圈可扩图研究
|
摘要
匹配理论是图论的主要研究专题之一,并且与其他理论课题具有密切联系.鉴于n-可扩图、导出匹配可扩图、PM-紧邻图的研究工作,我们提出两个新的概念：圈唯一可扩图和导出圈可扩图.称图G是圈唯一可扩图,如果对于图G的每一个偶圈C,G-V(C)有唯一的完美匹配.称图G是圈可扩图,如果去掉G的任意一个偶圈的顶点后得到的图有完美匹配.称图G是导出圈可扩图,如果去掉G的任意一个导出偶圈的顶点后得到的图有完美匹配.这里图G的一个圈C是导出圈,如果V(C)的导出子图是一个圈.显然,如果一个图是圈可扩图,那么它是导出圈可扩图.反之未必成立.
称图G是一个K3,3的H-培分,如果G≠K3,3但是G可由K3,3把它的一个哈密顿圈上的一些边换成奇路得到.用(?)来表示所有满足下面两个条件的图的集合：(i)G是极大外平面二部图；(ii)如果C为G的外部面的边界,那么C中恰有两条22-边(两个端点在G中的度均为2)且它们不相邻,C中其余的边为23-边(一个端点在G中的度大于等于3,另一个端点在G中的度为2).
本文我们主要研究圈唯一可扩二部图和导出圈可扩图,主要得到了下面的结果：
·图G是一个圈唯一可扩哈密顿二部图当且仅当G是K3,3或者G是(?)中的图的支撑哈密顿子图或者G是K3,3的H-部分；
.圈唯一可扩的一般二部图的部分刻画，
●一个图是导出圈可扩图的度和及最小度条件.
Matching theory is one of the important special topics of graph theory and is in connection with other theoretic problems closely. Motivated by the study of n-extendable graphs,IM-extendable graphs, and PM-compact graphs, we propose two new notions: cycle uniquely extendable graph and induced-cycle extendable graph. We say that a graph G is cycle uniquely extendable if G-V(C) has a unique perfect matching for any even cycle of G. We say that a graph G is cycle-extendable if G-V(C) has a perfect matching for any even cycle C of G. We say that a graph G is induced-cycle extendable if G-V(C) has a perfect matching for any induced even cycle C of G. Here, a cycle C of graph G is called an induced cycle if G[V(C)] is a cycle of G. Obviously, if a graph is cycle extendable, it is induced-cycle extendable. The converse is not true.
A graph G is called an H-subdivision of K3,3if G≠K3,3, but G can be obtained from K3,3by replacing some edges in a Hamilton cycle of K3,3by odd paths. Let (?) denote the set of all the graphs G which satisfy the following two conditions:(i) G is a maximal outerplane bipartite graph;(ii) if C is the boundary of the outer face of G, then C has only two22-edges (each of its two ends has degree2in G), which are not adjacent, the remaining edges of C are23-edges (in.G,one end of such edge has degree2and the other end has degree at least3).
In this paper, we study cycle uniquely extendable graphs and induced-cycle extend-able graphs. The main results are the following:
·A Hamiltonian bipartite graph G is cycle uniquely extendable if and only if G is K3,3or an H-subdivision of K3,3or a spanning Hamiltonian subgraph of the graph in (?);
·Partial characterizations of general bipartite graphs which are cycle uniquely ex-tendable;
·The conditions of a graph to be induced-cycle extendable.
称图G是一个K3,3的H-培分,如果G≠K3,3但是G可由K3,3把它的一个哈密顿圈上的一些边换成奇路得到.用(?)来表示所有满足下面两个条件的图的集合：(i)G是极大外平面二部图；(ii)如果C为G的外部面的边界,那么C中恰有两条22-边(两个端点在G中的度均为2)且它们不相邻,C中其余的边为23-边(一个端点在G中的度大于等于3,另一个端点在G中的度为2).
本文我们主要研究圈唯一可扩二部图和导出圈可扩图,主要得到了下面的结果：
·图G是一个圈唯一可扩哈密顿二部图当且仅当G是K3,3或者G是(?)中的图的支撑哈密顿子图或者G是K3,3的H-部分；
.圈唯一可扩的一般二部图的部分刻画，
●一个图是导出圈可扩图的度和及最小度条件.
Matching theory is one of the important special topics of graph theory and is in connection with other theoretic problems closely. Motivated by the study of n-extendable graphs,IM-extendable graphs, and PM-compact graphs, we propose two new notions: cycle uniquely extendable graph and induced-cycle extendable graph. We say that a graph G is cycle uniquely extendable if G-V(C) has a unique perfect matching for any even cycle of G. We say that a graph G is cycle-extendable if G-V(C) has a perfect matching for any even cycle C of G. We say that a graph G is induced-cycle extendable if G-V(C) has a perfect matching for any induced even cycle C of G. Here, a cycle C of graph G is called an induced cycle if G[V(C)] is a cycle of G. Obviously, if a graph is cycle extendable, it is induced-cycle extendable. The converse is not true.
A graph G is called an H-subdivision of K3,3if G≠K3,3, but G can be obtained from K3,3by replacing some edges in a Hamilton cycle of K3,3by odd paths. Let (?) denote the set of all the graphs G which satisfy the following two conditions:(i) G is a maximal outerplane bipartite graph;(ii) if C is the boundary of the outer face of G, then C has only two22-edges (each of its two ends has degree2in G), which are not adjacent, the remaining edges of C are23-edges (in.G,one end of such edge has degree2and the other end has degree at least3).
In this paper, we study cycle uniquely extendable graphs and induced-cycle extend-able graphs. The main results are the following:
·A Hamiltonian bipartite graph G is cycle uniquely extendable if and only if G is K3,3or an H-subdivision of K3,3or a spanning Hamiltonian subgraph of the graph in (?);
·Partial characterizations of general bipartite graphs which are cycle uniquely ex-tendable;
·The conditions of a graph to be induced-cycle extendable.
引文
[1]N. Anunchuen, A. Saito, Factor criticalty and complete closure of graphs, Discrete Mathe-matics,265(2003),13-21.
[2]J.A. Bondy, U.S.R. Murty, Graph Theory, Springer-Verlag, Berlin,2008.
[3]K. Cameron, Induced matchings, Discrete Applied Mathematics,24(1989),97-102.
[4]V. Chvatal, On certain polytopes associated with graphs, J.Combin.Theory Ser.B,18(1975), 138-154.
[5]O. Favaron, On κ-factor-critical graphs, Discussion Mathematics Graph Theory,16(1996), 41-51.
[6]O. Favaron, Extendability and factor-criticality, Discrete Mathematics,213(2000),115-122.
[7]O. Favaron, M.Y. Shi, Minimally k-factor-critical graphs, Australasian J. Combin.,17(1998), 89-97.
[8]T. Gallai, Neuer Beweis eines Tutte'schen Satzes, Magyar Tud. Akad. Mat. Kutato Int. Kozl,8(1963),135-139.
[9]P. Hanscn, F.J. Zhang, M.L. Zheng, Perfect matching and ears in elementary bipartite graphs, Discrete Mathematics,176(1997),131-138.
[10]G. Hetyei, Rectangular configurations which can be covered by 2 rectangles, Pecsi Tan. Foisk. Kozl,8(1964),351-367.
[11]D. Konig, Line system and determinants, Math. Termesz. Ert.,33(1915),221-229. (Hun-garian)
[12]L. Lovasz, M.D. Plummer, Matching Theory, Elsevier Science Publishers, B.V.North Hol-land,1986.
[13]L. Lovasz, On the structure of factorizable graphs, Acta Math. Acad. Sci. Hungar,23(1972), 179-195.
[14]J. Liu, X.M. Wang, A note on PM-compact bipartite graphs, Discussion Mathematics Graph Theory, accepted.
[15]Y. Liu, J.J. Yuan, S.Y. Wang, Degree conditions of IM-extendable graphs, Appl. Math. J. Chinese Univ. Ser. B,15(1)(2000),1-6.
[16]M.W. Padberf, M.R. Rao, The travelling salesman problem and a class of polyhedra of diameter two, Mathematics Program,7(1974),32-45.
[17]J. Petersen, Die theorie der regularengraphen, Acta Math.,15(1891),193-220.
[18]M.D. Plummer, On n-extendable graphs, Discrete Mathematics,31(1980),201-210.
[19]M.D. Plummer, Extendable matchings in graphs:a survey, Discrete Mathematics,127(1994), 277-292.
[20]A. Schrijver, Combinatorial Optimization:Polyhedra and Efficiency, Springer-Verlag, Berlin, 2003.
[21]Q. Wang, J.J. Yuan, Degree sum conditions of IM-extendable graphs, J. Zhengzhou Univer-sity,32(1)(2000),19-21.
[22]X.M. Wang, Y.X. Lin, M.H. Carvalho, C.L. Lucchesi, G. Sanjith, C.H. Little, A characteri-zation of PM-compact bipartite and near-bipartite graphs, Discrete Mathematics,313(2013), 772-783.
[23]X.M. Wang, W.P. Shang, Y.X. Lin, M. H. Carvalho, A characterization of PM-compact claw-free cubic graphs, submitted (2011).
[24]X.M. Wang, J.J. Yuan, Y.X. Lin, A characterization of PM-compact Hamiltonian bipartite graphs, Submitted.
[25]X.M. Wang, Y.X. Lin, Bipartite matching extendable graphs, Discrete Mathematics,308(2008), 5334-5341.
[26]X.M. Wang, Z.Z. Zhang, Y.X. Lin, Degree-type Conditions for Bipartite Matching Extend-ability, Ars Combinatoria,90(2009),295-305.
[27]R. Xu, Q.L. Yu, Degree-sum conditions for k-extendable graphs, Congr. Numer,63(2003)189-195.
[28]Q. Yu, Characterizations of various matching extensions in graphs, Australas J. Combin., 7(1993)55-64.
[29]J.J. Yuan, Induced matching extendable graphs, J. Graph Theory,28(1998),203-213.
[30]J. Zhou, J.J. Yuan, Characterization of induced matching extendable graphs with 2n vertices and 3n-1 edges, Australasian J. Combin.,33(2005),255-265.
[31]H.P. Zhang, F.J. Zhang, Plane elementary bipartite graphs, Discrete Mathematics,105(2000), 291-311.
[32]F. Zhang, R. Chen, When each hexagon of a hexagonal system covers it, Discrete Applied Mathematics,30(1991),63-75.
[2]J.A. Bondy, U.S.R. Murty, Graph Theory, Springer-Verlag, Berlin,2008.
[3]K. Cameron, Induced matchings, Discrete Applied Mathematics,24(1989),97-102.
[4]V. Chvatal, On certain polytopes associated with graphs, J.Combin.Theory Ser.B,18(1975), 138-154.
[5]O. Favaron, On κ-factor-critical graphs, Discussion Mathematics Graph Theory,16(1996), 41-51.
[6]O. Favaron, Extendability and factor-criticality, Discrete Mathematics,213(2000),115-122.
[7]O. Favaron, M.Y. Shi, Minimally k-factor-critical graphs, Australasian J. Combin.,17(1998), 89-97.
[8]T. Gallai, Neuer Beweis eines Tutte'schen Satzes, Magyar Tud. Akad. Mat. Kutato Int. Kozl,8(1963),135-139.
[9]P. Hanscn, F.J. Zhang, M.L. Zheng, Perfect matching and ears in elementary bipartite graphs, Discrete Mathematics,176(1997),131-138.
[10]G. Hetyei, Rectangular configurations which can be covered by 2 rectangles, Pecsi Tan. Foisk. Kozl,8(1964),351-367.
[11]D. Konig, Line system and determinants, Math. Termesz. Ert.,33(1915),221-229. (Hun-garian)
[12]L. Lovasz, M.D. Plummer, Matching Theory, Elsevier Science Publishers, B.V.North Hol-land,1986.
[13]L. Lovasz, On the structure of factorizable graphs, Acta Math. Acad. Sci. Hungar,23(1972), 179-195.
[14]J. Liu, X.M. Wang, A note on PM-compact bipartite graphs, Discussion Mathematics Graph Theory, accepted.
[15]Y. Liu, J.J. Yuan, S.Y. Wang, Degree conditions of IM-extendable graphs, Appl. Math. J. Chinese Univ. Ser. B,15(1)(2000),1-6.
[16]M.W. Padberf, M.R. Rao, The travelling salesman problem and a class of polyhedra of diameter two, Mathematics Program,7(1974),32-45.
[17]J. Petersen, Die theorie der regularengraphen, Acta Math.,15(1891),193-220.
[18]M.D. Plummer, On n-extendable graphs, Discrete Mathematics,31(1980),201-210.
[19]M.D. Plummer, Extendable matchings in graphs:a survey, Discrete Mathematics,127(1994), 277-292.
[20]A. Schrijver, Combinatorial Optimization:Polyhedra and Efficiency, Springer-Verlag, Berlin, 2003.
[21]Q. Wang, J.J. Yuan, Degree sum conditions of IM-extendable graphs, J. Zhengzhou Univer-sity,32(1)(2000),19-21.
[22]X.M. Wang, Y.X. Lin, M.H. Carvalho, C.L. Lucchesi, G. Sanjith, C.H. Little, A characteri-zation of PM-compact bipartite and near-bipartite graphs, Discrete Mathematics,313(2013), 772-783.
[23]X.M. Wang, W.P. Shang, Y.X. Lin, M. H. Carvalho, A characterization of PM-compact claw-free cubic graphs, submitted (2011).
[24]X.M. Wang, J.J. Yuan, Y.X. Lin, A characterization of PM-compact Hamiltonian bipartite graphs, Submitted.
[25]X.M. Wang, Y.X. Lin, Bipartite matching extendable graphs, Discrete Mathematics,308(2008), 5334-5341.
[26]X.M. Wang, Z.Z. Zhang, Y.X. Lin, Degree-type Conditions for Bipartite Matching Extend-ability, Ars Combinatoria,90(2009),295-305.
[27]R. Xu, Q.L. Yu, Degree-sum conditions for k-extendable graphs, Congr. Numer,63(2003)189-195.
[28]Q. Yu, Characterizations of various matching extensions in graphs, Australas J. Combin., 7(1993)55-64.
[29]J.J. Yuan, Induced matching extendable graphs, J. Graph Theory,28(1998),203-213.
[30]J. Zhou, J.J. Yuan, Characterization of induced matching extendable graphs with 2n vertices and 3n-1 edges, Australasian J. Combin.,33(2005),255-265.
[31]H.P. Zhang, F.J. Zhang, Plane elementary bipartite graphs, Discrete Mathematics,105(2000), 291-311.
[32]F. Zhang, R. Chen, When each hexagon of a hexagonal system covers it, Discrete Applied Mathematics,30(1991),63-75.