×

Degree sequences and edge connectivity. (English) Zbl 1388.05040

For each positive integer \(k\), one can associate a finite list \(C\)(\(k\)) of Bondy-Chvátal type conditions on a nondecreasing sequence \(d=(d_1,\dots ,d_n)\) of nonnegative integers such that every graph on \(n\) vertices with degree sequence at least \(d\) is \(k\)-edge-connected. These conditions are best possible in the sense that whenever one of them fails for \(d\) then there is a graph on \(n\) vertices with degree sequence at least \(d\) which is not \(k\)-edge-connected. In this connection, the author proves that \(C(k)\) is and must be large by showing that it contains \(p(k)\) many logically irredundant conditions, where \(p(k)\) is the number of partitions of \(k\). Furthermore, he demonstrates how to handle other types of edge-connectivity, such as, for example, essential \(k\)-edge-connectivity. It is also proved that any sublist equivalent to \(C(k)\) has length at least \(p(k)\), where \(p(k)\) is the number of partitions of \(k\), which is in contrast to the corresponding classic result on vertex connectivity where one needs just one such condition. Furthermore,he demonstrates how to handle other types of edge-connectivity, such as, for example, essential \(k\)-edge-connectivity. Finally, he informally describes a simple and fast procedure which generates the list \(C(k)\). Specialized to \(k=3\), this verifies a conjecture of D. Bauer et al. [Networks 54, No. 2, 95–98 (2009; Zbl 1207.05109)].

MSC:

05C07 Vertex degrees
05C40 Connectivity

Citations:

Zbl 1207.05109
Full Text: DOI

References:

[1] Bauer, D., Hakimi, L., Kahl, N., Schmeichel, E.: Sufficient degree conditions for \[k\] k-edge-connectedness of a graph. Networks 54, 95-98 (2009) · Zbl 1207.05109
[2] Boesch, F.: The strongest monotone degree condition for \[n\] n-connectedness of a graph. J. Combin. Theory Ser. B 16, 162-165 (1974) · Zbl 0262.05122 · doi:10.1016/0095-8956(74)90058-6
[3] Bondy, J.A.: Properties of graphs with constraints on degrees. Studia Sci. Math. Hungar. 4, 473-475 (1969) · Zbl 0184.27702
[4] Brualdi, R.A., Schmitt, J.R.: personal communication · JFM 46.0198.04
[5] Chvátal, V.: On Hamilton’s ideals. J. Combin. Theory Ser. B 16, 163-168 (1974) · Zbl 0213.50803
[6] Diestel, R.: Graph Theory, Graduate Texts in Mathematics, vol. 173, 3rd edn. Springer, Berlin (2005) · Zbl 1074.05001
[7] Gale, D.: A theorem on flows in networks. Pac. J. Math. 7, 1073-1082 (1957) · Zbl 0087.16303 · doi:10.2140/pjm.1957.7.1073
[8] Hardy, G.H., Ramanujan, S.: Asymptotic formulae in combinatory analysis. Proc. Lond. Math. Soc. 17, 75-115 (1918) · JFM 46.0198.04 · doi:10.1112/plms/s2-17.1.75
[9] Ryser, H.J.: Combinatorial properties of matrices of zeros and ones. Can. J. Math. 9, 371-377 (1957) · Zbl 0079.01102 · doi:10.4153/CJM-1957-044-3
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.