×

Deficiency and forbidden subgraphs of connected, locally-connected graphs. (English) Zbl 1430.05067

Summary: A graph \(G\) is locally-connected if the neighbourhood \(N_G(v)\) induces a connected subgraph for each vertex \(v\) in \(G\). For a graph \(G\), the deficiency of \(G\) is the number of vertices unsaturated by a maximum matching, denoted by \(\operatorname{def}(G)\). In fact, the deficiency of a graph measures how far a maximum matching is from being perfect matching. A. Saito and L. Xiong [ibid. 36, No. 3, 621–628 (2016; Zbl 1339.05219)] have studied subgraphs, the absence of which forces a connected and locally-connected graph \(G\) of sufficiently large order to satisfy \(\operatorname{def}(G) \leq 1\). In this paper, we extend this result to the condition of \(\operatorname{def}(G) \leq k\), where \(k\) is a positive integer. Let \(\beta_0 = \left\lceil\frac{1}{2} ( 3 + \sqrt{8k + 17} )\right\rceil - 1 \), we show that \(K_{1,2}, K_{1,3} , \dots, K_{1, \beta_0}, K_3\) or \(K_2 \vee 2K_1\) is the required forbidden subgraph. Furthermore, we obtain some similar results about 3-connected, locally-connected graphs.

MSC:

05C40 Connectivity
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Citations:

Zbl 1339.05219
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Adamaszek, M. Adamaszek, M. Mnich and J.M. Schmidt, Lower bounds for locally highly connected graphs, Graphs Combin. 32 (2016) 1641-1650. doi:10.1007/s00373-016-1686-y; · Zbl 1349.05192
[2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, Elsevier, New York, 1976).; · Zbl 1226.05083
[3] C. Brause, D. Rautenbach and I. Schiermeyer, Local connectivity, local degree conditions, some forbidden induced subgraphs, and cycle extendability, Discrete Math. 340 (2017) 596-606. doi:10.1016/j.disc.2016.11.035; · Zbl 1355.05144
[4] G. Chartrand and R.E. Pippert, Locally connected graphs, Časopis Pěst. Mat. 99 (1974) 158-163.; · Zbl 0278.05113
[5] X.D. Chen, M.C. Li, W. Liao and H. Broersma, Hamiltonian properties of almost locally connected claw-free graphs, Ars Combin. 124 (2016) 95-109.; · Zbl 1413.05200
[6] R. Faudree, E. Flandrin and Z. Ryjáček, Claw-free graphs—A survey, Discrete Math. 164 (1997) 87-147. doi:10.1016/S0012-365X(96)00045-3; · Zbl 0879.05043
[7] M. Jünger, G. Reinelt and W.R. Pulleyblank, On partitioning the edges of graphs into connected subgraphs, J. Graph Theory 9 (1985) 539-549. doi:10.1002/jgt.3190090416; · Zbl 0665.05040
[8] M. Las Vergnas, A note on matchings in graphs, Colloque sur la Théorie des Graphes, Cahiers CentreÉtudes Rech. Opér. 17 (1975) 257-260.; · Zbl 0315.05123
[9] D.J. Oberly and D.P. Sumner, Every connected, locally connected nontrivial graph with no induced claw is Hamiltonian, J. Graph Theory 3 (1979) 351-356. doi:10.1002/jgt.3190030405; · Zbl 0424.05036
[10] M.D. Plummer and A. Saito, Forbidden subgraphs and bounds on the size of a maximum matching, J. Graph Theory 50 (2005) 1-12. doi:10.1002/jgt.20087; · Zbl 1070.05070
[11] X.Y. Qu and H.Y. Lin, Quasilocally connected, almost locally connected or triangularly connected claw-free graphs, Lect. Notes Comput. Sci. 4381 (2007) 162-165. doi:10.1007/978-3-540-70666-3_17; · Zbl 1149.05320
[12] A. Saito and L.M. Xiong, The Ryjáček closure and a forbidden subgraph, Discuss. Math. Graph Theory 36 (2016) 621-628. doi:10.7151/dmgt.1876; · Zbl 1339.05219
[13] D.P. Sumner, 1-factors and antifactor sets, J. Lond. Math. Soc. 2 (13) (1976) 351-359. doi:10.1112/jlms/s2-13.2.351; · Zbl 0338.05118
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.