View in EDS

The minimum size of graphs satisfying cut conditions.

Saved in:
Bibliographic Details
Title: The minimum size of graphs satisfying cut conditions.
Authors: Jobson, Adam S.1, Kézdy, André E.1, Lehel, Jenő1,2 j0lehe01@louisville.edu
Source: Discrete Applied Mathematics. Mar2018, Vol. 237, p89-96. 8p.
Subjects: Graph theory, Paths & cycles in graph theory, Topological degree, Mathematical bounds, Bisectors (Geometry)
Abstract: A graph G of order n satisfies the cut condition (CC) if there are at least | A | edges between any set A ⊂ V ( G ) , | A | ≤ n ∕ 2 , and its complement A ¯ = V ( G ) ∖ A . For even n , G satisfies the even cut condition (ECC), if [ A , A ¯ ] contains at least n ∕ 2 edges, for every A ⊂ V ( G ) , | A | = n ∕ 2 . We investigate here the minimum number of edges in a graph G satisfying CC or ECC. A simple counting argument shows that for both cut conditions | E ( G ) | ≥ n − 1 , and the star K 1 , n − 1 is extremal. Faudree et al. (1999) conjectured that the extremal graphs with maximum degree Δ ( G ) < n − 1 satisfying ECC have 3 n ∕ 2 − O ( 1 ) edges. Here we prove the tight bound | E ( G ) | ≥ 3 n ∕ 2 − 3 , for every graph G with Δ ( G ) < n − 1 and satisfying CC. If G is 2-connected and satisfies ECC, we prove that | E ( G ) | ≥ 3 n ∕ 2 − 2 holds and tight, for every even n . We obtain the weaker bound | E ( G ) | ≥ 5 n ∕ 4 − 2 , for every graph of order n ≡ 0 ( mod 4 ) with Δ ( G ) < n − 1 and satisfying ECC; meanwhile we conjecture that | E ( G ) | ≥ 3 n ∕ 2 − 4 holds, for every even n . [ABSTRACT FROM AUTHOR]
Copyright of Discrete Applied Mathematics is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:A graph G of order n satisfies the cut condition (CC) if there are at least | A | edges between any set A ⊂ V ( G ) , | A | ≤ n ∕ 2 , and its complement A ¯ = V ( G ) ∖ A . For even n , G satisfies the even cut condition (ECC), if [ A , A ¯ ] contains at least n ∕ 2 edges, for every A ⊂ V ( G ) , | A | = n ∕ 2 . We investigate here the minimum number of edges in a graph G satisfying CC or ECC. A simple counting argument shows that for both cut conditions | E ( G ) | ≥ n − 1 , and the star K 1 , n − 1 is extremal. Faudree et al. (1999) conjectured that the extremal graphs with maximum degree Δ ( G ) < n − 1 satisfying ECC have 3 n ∕ 2 − O ( 1 ) edges. Here we prove the tight bound | E ( G ) | ≥ 3 n ∕ 2 − 3 , for every graph G with Δ ( G ) < n − 1 and satisfying CC. If G is 2-connected and satisfies ECC, we prove that | E ( G ) | ≥ 3 n ∕ 2 − 2 holds and tight, for every even n . We obtain the weaker bound | E ( G ) | ≥ 5 n ∕ 4 − 2 , for every graph of order n ≡ 0 ( mod 4 ) with Δ ( G ) < n − 1 and satisfying ECC; meanwhile we conjecture that | E ( G ) | ≥ 3 n ∕ 2 − 4 holds, for every even n . [ABSTRACT FROM AUTHOR]
ISSN:0166218X
DOI:10.1016/j.dam.2017.11.014