正则图的独立集与团横贯
|
摘要
随着时代的进步以及计算机科学的高速发展,图论在实际中的应用越来越广泛,关于图论的研究也就具有重要的现实意义.在图论中,由于受到来自不同领域的实际问题的驱动和对图的结构分析的需要,产生了许多图参数,这些图参数不仅在图的理论研究中占有重要的地位,同时又与图的应用密不可分.因此,图参数的研究始终是图论中最重要的研究内容.
本文主要对具有较小度数的正则图,研究了其独立数和团横贯数并刻画了相应的极值图.其次,还讨论了它们的割边、割点和匹配数.其主要结果可以概括如下：
·在第二章,我们首先利用数学归纳法对2-连通不含4阶完全子图的无爪4-正则图的独立数给出了一个确定的值；(相关结果发表在《Taiwanese J.Math.》上).然后利用线图的相关知识得到了连通不含4阶完全子图的无爪4-正则图的独立数的下界及极值图的刻画.
·在第三章,我们首先对于2-连通不含4阶完全子图的无爪4-正则图的团横贯数呈现了一个确定的值；(相关结果被《Acta Math.Sin.(Engl.Ser.)》录用).接着,我们研究了3-正则图的线图的团横贯数的上界与达到该上界的极值图的刻画,利用这个结果自然而然的得出了连通不含4阶完全子图的无爪4-正则图的团横贯数的上界与极值图的刻画；最后我们研究了连通无三角形的3-正则图的匹配数的下界以及达到该下界的极值图,并根据该结果对连通无三角形的3-正则图的线图的团横贯数给出了一个上界并刻画了达到这个上界的极值图.
·在第四章,我们主要研究了正则图的有关最大团横贯数的取值情况.首先对团数为k的k-正则图的最大团横贯数的上界、无爪3-正则图的最大团横贯数的下界以及达到相应界的极值图的刻画进行了讨论；接着讨论了团数至少为3的任意图的符号最大团横贯数的紧的下界、团数为k的k-正则图的符号最大团横贯数的上界与极值图的刻画、无爪3-正则图的符号最大团横贯数的下界与极值图的刻画、不含4阶完全子图的无爪4-正则图的符号最大团横贯数的上界与下界及达到下界的极值图的刻画；(相关结果发表在《Int.J.Comput.Math.》上).最后对团数至少为3的任意图的减最大团横贯数的下界与团数为k的k-正则图的减最大团横贯数的上界进行了讨论.
·在第五章,我们主要研究了一般4-正则图、无爪4-正则图、不含4阶完全子图的无爪4正则图的末块数与割点数的上界与极值图的刻画,(相关结果已被《Discuss. Math.Graph Theory》录用).同时,对于无三角形的3-正则图的割边数,我们给出了一个上界并刻画了达到这个上界的极值图.
As time progresses and computer science rapidly develop, the graph theory is widely used in practice, and so the study to it has great realistic significance. In graph theory, due to the drive by practical problems from different fields and the need for the structure analysis of the graph, many graph parameters emerged. The graph parameters not only play important role in the theory research of graph, but also go inseparable from the application of graph. Therefore, the research on graph parameters is always the most important research in graph theory.
In this thesis, for the regular graph with a smaller degree, we investigate its independence number and clique-transversal number, and we characterize the extremal graphs accordingly. Meanwhile, we study its cut-edges, cut-vertices and matching number. The main results can be generalize as the following:
In Chapter2, firstly, we give an exactly value on the independence number for2-connected claw-free4-regular graphs without complete subgraph of order4by applying mathematical induction. Secondly, we get the lower bound and the characterization of extremal graphs achieving the bound on the independence number for connected claw-free4-regular graphs without complete subgraph of order4by applying the related knowledge of line graph.
In Chapter3, firstly, we present an exactly value on the clique-transversal number for2-connected claw-free4-regular graphs without complete subgraph of order4. In the following, we investigate the upper bound on the clique-transversal number for the line graphs of cubic graphs and the characterization of extremal graphs achieving the bound. As a natural result, we get the upper bound and the characterization of extremal graphs achieving the bound on the clique-transversal number for connected claw-free4-regular graphs without complete subgraph of or-der4. At last, we investigate the lower bound and the characterization of extremal graphs achieving the bound on the matching number for connected triangle-free cu-bic graphs. By this result, we get an upper bound on the clique-transversal number of the line graphs of connected triangle-free cubic graphs and we characterize the extremal graphs achieving the upper bound.
In Chapter4, we consider the range of the maximum-clique transversal num-ber for regular graphs. First, we discuss the upper bound on the maximum-clique transversal number for the k-regular graphs of clique number k, the lower bound on the maximum-clique transversal number for the claw-free cubic graphs and the characterization of extremal graphs. Next, we investigate the tight lower bound on the signed maximum-clique transversal number for arbitrarily graph with the clique number at least3, the upper bound on the signed maximum-clique transver-sal number for the k-regular graphs of clique number k and the characterization of extremal graphs, the lower bound on the signed maximum-clique transversal num-ber for the claw-free cubic graphs and the characterization of extremal graphs, the tight upper bound and the lower bound on the signed maximum-clique transversal number for the claw-free4-regular graphs without complete subgraph of order4and the characterization of extremal graphs achieving the the lower bound. Finally, we discuss the lower bound on the minus maximum-clique transversal number for arbitrarily graph with clique number at least3and the upper bound on the minus maximum-clique transversal number for the k-regular graphs of clique number k.
In Chapter5, we investigate the upper bounds on the end-blocks number and cut-vertices number for4-regular graphs, claw-free4-regular graphs, claw-free4-regular graphs without complete subgraph of order4, respectively, and characterize the extremal graphs achieving these bounds. Meanwhile, for the cut-edges number of the triangle-free cubic graphs, we give the upper bound, and characterize the extremal graphs achieving this bound.
本文主要对具有较小度数的正则图,研究了其独立数和团横贯数并刻画了相应的极值图.其次,还讨论了它们的割边、割点和匹配数.其主要结果可以概括如下：
·在第二章,我们首先利用数学归纳法对2-连通不含4阶完全子图的无爪4-正则图的独立数给出了一个确定的值；(相关结果发表在《Taiwanese J.Math.》上).然后利用线图的相关知识得到了连通不含4阶完全子图的无爪4-正则图的独立数的下界及极值图的刻画.
·在第三章,我们首先对于2-连通不含4阶完全子图的无爪4-正则图的团横贯数呈现了一个确定的值；(相关结果被《Acta Math.Sin.(Engl.Ser.)》录用).接着,我们研究了3-正则图的线图的团横贯数的上界与达到该上界的极值图的刻画,利用这个结果自然而然的得出了连通不含4阶完全子图的无爪4-正则图的团横贯数的上界与极值图的刻画；最后我们研究了连通无三角形的3-正则图的匹配数的下界以及达到该下界的极值图,并根据该结果对连通无三角形的3-正则图的线图的团横贯数给出了一个上界并刻画了达到这个上界的极值图.
·在第四章,我们主要研究了正则图的有关最大团横贯数的取值情况.首先对团数为k的k-正则图的最大团横贯数的上界、无爪3-正则图的最大团横贯数的下界以及达到相应界的极值图的刻画进行了讨论；接着讨论了团数至少为3的任意图的符号最大团横贯数的紧的下界、团数为k的k-正则图的符号最大团横贯数的上界与极值图的刻画、无爪3-正则图的符号最大团横贯数的下界与极值图的刻画、不含4阶完全子图的无爪4-正则图的符号最大团横贯数的上界与下界及达到下界的极值图的刻画；(相关结果发表在《Int.J.Comput.Math.》上).最后对团数至少为3的任意图的减最大团横贯数的下界与团数为k的k-正则图的减最大团横贯数的上界进行了讨论.
·在第五章,我们主要研究了一般4-正则图、无爪4-正则图、不含4阶完全子图的无爪4正则图的末块数与割点数的上界与极值图的刻画,(相关结果已被《Discuss. Math.Graph Theory》录用).同时,对于无三角形的3-正则图的割边数,我们给出了一个上界并刻画了达到这个上界的极值图.
As time progresses and computer science rapidly develop, the graph theory is widely used in practice, and so the study to it has great realistic significance. In graph theory, due to the drive by practical problems from different fields and the need for the structure analysis of the graph, many graph parameters emerged. The graph parameters not only play important role in the theory research of graph, but also go inseparable from the application of graph. Therefore, the research on graph parameters is always the most important research in graph theory.
In this thesis, for the regular graph with a smaller degree, we investigate its independence number and clique-transversal number, and we characterize the extremal graphs accordingly. Meanwhile, we study its cut-edges, cut-vertices and matching number. The main results can be generalize as the following:
In Chapter2, firstly, we give an exactly value on the independence number for2-connected claw-free4-regular graphs without complete subgraph of order4by applying mathematical induction. Secondly, we get the lower bound and the characterization of extremal graphs achieving the bound on the independence number for connected claw-free4-regular graphs without complete subgraph of order4by applying the related knowledge of line graph.
In Chapter3, firstly, we present an exactly value on the clique-transversal number for2-connected claw-free4-regular graphs without complete subgraph of order4. In the following, we investigate the upper bound on the clique-transversal number for the line graphs of cubic graphs and the characterization of extremal graphs achieving the bound. As a natural result, we get the upper bound and the characterization of extremal graphs achieving the bound on the clique-transversal number for connected claw-free4-regular graphs without complete subgraph of or-der4. At last, we investigate the lower bound and the characterization of extremal graphs achieving the bound on the matching number for connected triangle-free cu-bic graphs. By this result, we get an upper bound on the clique-transversal number of the line graphs of connected triangle-free cubic graphs and we characterize the extremal graphs achieving the upper bound.
In Chapter4, we consider the range of the maximum-clique transversal num-ber for regular graphs. First, we discuss the upper bound on the maximum-clique transversal number for the k-regular graphs of clique number k, the lower bound on the maximum-clique transversal number for the claw-free cubic graphs and the characterization of extremal graphs. Next, we investigate the tight lower bound on the signed maximum-clique transversal number for arbitrarily graph with the clique number at least3, the upper bound on the signed maximum-clique transver-sal number for the k-regular graphs of clique number k and the characterization of extremal graphs, the lower bound on the signed maximum-clique transversal num-ber for the claw-free cubic graphs and the characterization of extremal graphs, the tight upper bound and the lower bound on the signed maximum-clique transversal number for the claw-free4-regular graphs without complete subgraph of order4and the characterization of extremal graphs achieving the the lower bound. Finally, we discuss the lower bound on the minus maximum-clique transversal number for arbitrarily graph with clique number at least3and the upper bound on the minus maximum-clique transversal number for the k-regular graphs of clique number k.
In Chapter5, we investigate the upper bounds on the end-blocks number and cut-vertices number for4-regular graphs, claw-free4-regular graphs, claw-free4-regular graphs without complete subgraph of order4, respectively, and characterize the extremal graphs achieving these bounds. Meanwhile, for the cut-edges number of the triangle-free cubic graphs, we give the upper bound, and characterize the extremal graphs achieving this bound.
引文
[1]T. Andreae, On the clique-transversal number of chordal graphs, Discrete Math. 191 (1998),3-11.
[2]M. Aigner, T. Andreae, Vertex-sets that meet all maximal cliques of a graph, manuscript,1986.
[3]M.O. Albertson and D.M. Berman, The number of cut-Vertices in a graph of given minimum degree, Discrete Math.89 (1991),97-100.
[4]M.O. Albertson, B. Bollobas, and S. Tucker, The independence ratio and the maximum degree of a graph, Congr. Numer.17 (1976),43-50.
[5]T. Andreae, C. Flotow, On covering all cliques of a chordal graph, Discrete Math.149 (1996),299-302.
[6]M.O. Albertson, R.Haas, The edge chromatic difference sequence of a cubic graaph, Discrete Math.177 (1997),1-8.
[7]T. Andreae, M. Schughart and Zs. Tuza, Clique-transversal sets of line graphs and complements of line graphs, Discrete Math.88 (1991),11-20.
[8]C. Berge, Hypergraphs, Amsterdam:North-Holland,1989.
[9]C. Berge, Sur le couplage maximum d'un graphe, C. R. Acad. Sci. Paris 247 (1958) 258-259.
[10]B. Bollobas, Modern Graph Theory, New York:Springer-Verlag,2001.
[11]R.L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc.37 (1941),194-197.
[12]S. Brandt, Triangle-free graphs whose independence number equals the degree, Discrete Math.310 (2010),662-669.
[13]L.W. Beineke, Derived graphs and digraphs, in beitrage zur Graphentheorie. Teubner Leipzig (1968),17-33.
[14]B. Bajnok, G. Brinkmann, On the independence number of triangle-free graphs with maximum degree three, J. Combin. Math. Combin. Comput.26 (1998), 237-254.
[15]A. Brandstadt, V. D. Chepoi, and F. F. Dragan, Clique r-domination and clique r-packing problems on dually chordal graphs, SIAM J. Discrete Math. 10 (1997),109-127.
[16]F. Bonomo, M. Chudnovsky and G. Duran, Partial characterizations of clique-perfect graphs I:Subclasses of claw-free graphs, Discrete Appl. Math.156 (2008),1058-1082.
[17]F. Bonomo, M. Chudnovsky and G. Duran, Partial characterizations of clique-perfect graphs II:Diamond-free and Helly circular-arc graphs, Discrete Appl. Math.309 (2009),3485-3499.
[18]T. Biedl, E.D. Demaine, C.A. Duncan, R. Fleischer, and S.G. Kobourov, Tight bounds on maximal and maximum matchings, Discrete Math 285 (2004),7-15.
[19]F. Bonomo, G. Duran, F. Soulignac, and G. Sueiro, Partial characterizations of clique-perfect and coordinated graphs:superclasses of triangle-free graphs, Electronic Notes in Discrete Math.30 (2008),51-56
[20]G. Bacso. S. Gravier, A. Gyarfas, M. Preissmann and A. Sebo, Coloring the maximal cliques of graphs, SIAM J. Discrete Math.17 (2004),361-376.
[21]V. Balachandhran, P. Nagavamsi and C.P. Rangan, Clique transversal and clique independence on comparability graphs, Inform. Process. Lett.58 (1996), 181-184.
[22]G. Bacso, Zs. Tuza, Clique-transversal sets and weak 2-coloringsin graphs of small maximum degree, Discrete Mathematics and Theoretical Computer Sci-ence 11 (2) (2009),15-24.
[23]M.S. Chang, Y.H. Chen, G. J. Chang and J. H. Yan, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, Discret Appl. Math.66 (1996),189-203.
[24]L.H. Clark and R.C. Entringer, The number of cut vertices in graphs with given minimum degree, Discrete Math.18 (1990),137-145.
[25]G.J. Chang, M. Farber and Zs. Tuza, Algorithmic aspects of neighbourhood numbers, SIAM J. Discrete Math.6 (1993),24-29.
[26]G.J. Chang, M.J. Jou, The number of maximal independent sets in connected triangle-free graphs, Discrete Math.197/198 (1999),169-178.
[27]M.S. Chang, T. Kloks and C.M. Lee, Maximum clique transversals, In:Pro-ceedings of the 27th international workshop on graph-theoretic concepts in com-puter science. Lecture notes in computer science 2204 (2001),32-43.
[28]G. Chartrand, S.F. Kapoor, L. Lesniak, and S. Schuster, Near 1-factors in graphs, Proc. Fourteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, Congress Numerantium 41 (1984),131-147.
[29]G. Chartrand and L. Lesniak, Graphs and Digraphs,2nd Edition, Wadsworth and Brooks/Cole, Monterey, California,1986.
[30]J.E. Dunbar, S.T. Hedetniemi, M.A. Henning, and P. J. Slater, Signed dom-ination in graphs, in Graph Theory, Combinatorics, and Applications, John Wiley and Sons, Inc.1 (1995),311-322.
[31]G. Duran, M.C. Lin, S. Mera, J.L. Szwarcfter, Algorithms for finding clique-transversals of graphs, Annals of Operations Research 157 (2008),37-45.
[32]G. Duran, M.C. Lin and J.L. Szwarcfter, On clique-transversals and clique-independent sets, Annals of Operations Research 116 (2002),71-77.
[33]E. Dahlhaus, P.D. Mannuel and M. Mill, Maximum h-colourable subgraph problem in balanced graphs, Inform. Process. Lett.65 (1998),301-303.
[34]P. Erdos, T. Gallai and Zs. Tuza, Covering the cliques of a graph with vertices, Discrete Math.108 (1992),279-289.
[35]S. Fajtlowicz, The independence ratio for cubic graphs, Congr. Numer.19 (1977),273-277. [Proceedings of the Eighth Southeastern on Combinatorics, Graph Theory and Computing, Baton Rouge].
[36]S. Fajtlowicz, On the size of independent sets in graphs, Congr. Numer.21 (1978),269-274.
[37]K.L. Fraughnaugh, Independence in graphs with maximum degree four, J. Combin. Theory Ser. B 37 (1984),254-269.
[38]K.L. Fraughnaugh, Size and independence in triangle-free graphs with maxi-mum degree three, J. Graph Theory 14 (1990),525-535.
[39]R.J. Faudree, R.J. Gould, M.S. Jacobson, L.M. Lesniak and T.E. Lindquester, On independent generalized degrees and independence numbers in K(1, m)-free graphs, Discrete Math.103 (1992),17-24.
[40]K.L. Fraughnaugh and S.C. Locke, 11/30(finding large independent sets in connected triangle-free 3-regular graphs), J. Combin. Theory Ser. B 65 (1995), 51-72.
[41]K.L. Fraughnaugh and S.C. Locke, Finding independent sets in triangle-free graphs, SIAM J. Discrete Math.9 (1996),674-681.
[42]T. Gallai, Uber extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest, Eotvos Sect. Math.2 (1959),133-138.
[43]J.R. Griggs and C.M. Grinstead, D.R. Guichard, The number of maximal independent sets in a connected graph, Discrete Math.68 (1988),211-220.
[44]W. Goddard and M. A. Henning, Domination in planar graphs with small diameter, J. Graph Theory 40 (2002),1-25.
[45]J.R. Griggs and O. Murphy, Edge density and independence ratio in triangle-free graphs with maximum degree three, Discrete Math.152 (1996),157-170.
[46]V. Guruswami, C.P. Rangan, Algorithmic aspects of clique-transvsal and clique-independent sets, Discrete Appl. Math.100 (2000),183-202.
[47]C.C. Heckman, On the tightness of the 5/14 independence ratio, Discrete Math.308 (2008),3169-3179.
[48]J. Harant, A lower bound on the independence number of a graph, Discrete Math.188 (1998),139-243.
[49]J. Harant, M.A. Henning, D. Rautenbach, I. Schiermeyer, The independence number in graphs of maximum degree three, Discrete Math.308 (2008),5829-5833.
[50]M.A. Henning, L.Y. Kang, E.F. Shan, A. Yeo, On matching and total domi-nation in graphs, Discrete Math.308 (2008),2313-2318.
[51]J. Harant, I. Schiermeyer, On the independence number of a graph in terms of order and size, Discrete Math.232 (2001),131-138.
[52]A.M. Hobbs, E. Schmeichel, On the maximum number of independent edges in cubic graphs, Discrete Math.42 (1982),317-320.
[53]C.C. Heckman, R. Thomas, A new proof of the independence ratio of triangle-free cubic graphs, Discrete Math.233 (2001),233-237.
[54]C.C. Heckman, R. Thomas, Independent sets in triangle-free cubic planar graphs, J. Combin. Theory, Ser. B 96 (2006),253-275.
[55]M.A. Henning and A. Yeo, Tight lower bounds on the size of a maximum matching in a regular graph, Graphs and Combinatorics.23 (2007),647-657.
[56]K.F. Jones, Size and independence in triangle-free graphs with maximum de-gree three, J. Graph Theory 14(5) (1990),525-535.
[57]D.L. Kreher and S.P. Radziszowski, Minimum triangle-free graphs, Ars Com-binatoria 31 (1991),65-92.
[58]S.C. Locke, Bipartite density and the independence ratio, J. Graph Theory 10 (1986),47-53.
[59]C.M. Lee, Variations of maximum-clique transversal sets on graphs, Annals of Operations Research 181 (1) (2010),21-66.
[60]C.M. Lee, M.S. Chang, Distance-hereditary graphs are clique-perfect, Discrete Appl. Math.154 (2006),525-536.
[61]C.M. Lee, M.S.Chang, Signed and minus clique-transversal functions on graphs, Inform. Process. Lett.109 (2009),414-417.
[62]S.C. Locke, F. Lou, Finding independent sets in K4-hee 4-regular connected graphs, J. Combin. Theory, Ser. B 71 (1997),85-110.
[63]L. Lovasz and M.D. Plummer, Matching Theory, Ann. Discrete Math.29 (1986).
[64]P.S. Loh, B. Sudakov, Independent transversals in locally sparse graphs, J. Combin. Theory, Ser. B 97 (2007),904--918.
[65]Z.S. Liang, E.F. Shan, T.C.E. Cheng, Clique-transversal sets in cubic graphs. In Chen, B., Paterson, M., Zhang, G. (Eds.):ESCAPE 2007, Lecture Notes in Comput. Sci.,4614, Springer-Verlag,107-115 (2007)
[66]J. Lehel and Z. Tuza, Neighborhood perfect graphs, Discrete Math.61 (1986), 93-101.
[67]H. Li and C. Virlouvet, Neighborhood conditions for claw-free hamiltonian graphs, Ars Combin.29A (1990),109-116.
[68]S.A. Lakshmanan, A. Vijayakumar, The< t>-property of some classes of graphs, Discrete Math.309(2009),259-263.
[69]A. Nirmala and A.R. Rao, On the number of cut edges in a regular graph, Australasian Journal of Combinatorics 27 (2003),5-12.
[70]K. Nirmala and A.R. Rao, The number of cut vertices in a regular graph, Cahiers Centre Etudes Reserche Oper.17 (1975),295-299.
[71]Suil O and D.B. West, Matching and edge-connectivity in regular graphs, European Journal of Combinatorics 32 (2011),324-329.
[72]Suil O, D.B. West, Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree, J. Graph Theory 64 (2010),116-131.
[73]J. Petersen, Die theorie der regularen graph. Acta Math.15 (1891),193-220.
[74]M.D. Plummer, Extending matchings in claw-free graphs, Discrete Math.125 (1994),301-307.
[75]A.R. Rao, An extremal problem in graph theory, Israel J. Math.6 (1968), 261-266.
[76]A.R. Rao, Some extremal problems and characterizations in the theory of graphs, Ph. D. Thesis, Indian Statistical Institute (1969).
[77]S.B. Rao, Contributions to the theory of directed and undirected graphs, Ph. D. Thesis, Indian Statistical Institute (1970).
[78]D. Rautenbach, On vertex orderings and the stability number in triangle-free graphs, Discrete Math.231 (2001),411-420.
[79]Z. Ryjacek, I. Schiermeyer, On the independence number in-K1,r+1-free graphs, Discrete Math.138 (1995),365-374.
[80]W. Staton, Some Ramsey-type numbers and the independence ratio, Trans. Amer. Math. Soc.256 (1979),353-370.
[81]E.F. Shan, T.C.E. Cheng and L.Y. Kang, Bounds on the clique-transversal number of regular graphs, Science in China A:Mathematics 51 (5) (2008), 851-863.
[82]E.F. Shan, L.Y. Kang, Clique-transversal sets in 4-regular claw-free graphs, Acta Mathematica Sinica 27 (2011),883-890.
[83]E.F. Shan, H.C. Wang, Claw-free cubic graphs with clique-transversal number one-half their order, Appl. math. lett.24(7) 2011,1080-1083.
[84]Zs. Tuza, Covering all cliques of a graph, Discrete Math.86 (1990),117-126.
[85]W.T. Tutte, Connectivity in Graphs, University of Toronto Press, Toronto, 1966.
[86]H.C. Wang, L.Y. Kang, E.F. Shan, Signed clique-transversal functions in graphs, Int. J. Comput. math.87(11) (2010),2398-2407.
[87]徐保根,关于图的团符号控制数,系统科学与数学,28(2008),282-287.
[88]G.J. Xu, E.F. Shan, L.Y. Kang, T.C.E. Cheng, The algorithmic complexity of the minus clique-transversal problem, Appl. Math, and Computation 189 (2007),1410-1418.
[89]R. Yuster, Finding and counting cliques and independent sets in r-uniform hypergraphs, Inform. Process. Lett.99 (2006),130-134.
[90]R. Zenklusen, B. Ries, C. Picouleau, D. de Werra, M.-C. Costa, C. Bentz, Blockers and transversals, Discrete Math.309 (2009),4306-4314.
[2]M. Aigner, T. Andreae, Vertex-sets that meet all maximal cliques of a graph, manuscript,1986.
[3]M.O. Albertson and D.M. Berman, The number of cut-Vertices in a graph of given minimum degree, Discrete Math.89 (1991),97-100.
[4]M.O. Albertson, B. Bollobas, and S. Tucker, The independence ratio and the maximum degree of a graph, Congr. Numer.17 (1976),43-50.
[5]T. Andreae, C. Flotow, On covering all cliques of a chordal graph, Discrete Math.149 (1996),299-302.
[6]M.O. Albertson, R.Haas, The edge chromatic difference sequence of a cubic graaph, Discrete Math.177 (1997),1-8.
[7]T. Andreae, M. Schughart and Zs. Tuza, Clique-transversal sets of line graphs and complements of line graphs, Discrete Math.88 (1991),11-20.
[8]C. Berge, Hypergraphs, Amsterdam:North-Holland,1989.
[9]C. Berge, Sur le couplage maximum d'un graphe, C. R. Acad. Sci. Paris 247 (1958) 258-259.
[10]B. Bollobas, Modern Graph Theory, New York:Springer-Verlag,2001.
[11]R.L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc.37 (1941),194-197.
[12]S. Brandt, Triangle-free graphs whose independence number equals the degree, Discrete Math.310 (2010),662-669.
[13]L.W. Beineke, Derived graphs and digraphs, in beitrage zur Graphentheorie. Teubner Leipzig (1968),17-33.
[14]B. Bajnok, G. Brinkmann, On the independence number of triangle-free graphs with maximum degree three, J. Combin. Math. Combin. Comput.26 (1998), 237-254.
[15]A. Brandstadt, V. D. Chepoi, and F. F. Dragan, Clique r-domination and clique r-packing problems on dually chordal graphs, SIAM J. Discrete Math. 10 (1997),109-127.
[16]F. Bonomo, M. Chudnovsky and G. Duran, Partial characterizations of clique-perfect graphs I:Subclasses of claw-free graphs, Discrete Appl. Math.156 (2008),1058-1082.
[17]F. Bonomo, M. Chudnovsky and G. Duran, Partial characterizations of clique-perfect graphs II:Diamond-free and Helly circular-arc graphs, Discrete Appl. Math.309 (2009),3485-3499.
[18]T. Biedl, E.D. Demaine, C.A. Duncan, R. Fleischer, and S.G. Kobourov, Tight bounds on maximal and maximum matchings, Discrete Math 285 (2004),7-15.
[19]F. Bonomo, G. Duran, F. Soulignac, and G. Sueiro, Partial characterizations of clique-perfect and coordinated graphs:superclasses of triangle-free graphs, Electronic Notes in Discrete Math.30 (2008),51-56
[20]G. Bacso. S. Gravier, A. Gyarfas, M. Preissmann and A. Sebo, Coloring the maximal cliques of graphs, SIAM J. Discrete Math.17 (2004),361-376.
[21]V. Balachandhran, P. Nagavamsi and C.P. Rangan, Clique transversal and clique independence on comparability graphs, Inform. Process. Lett.58 (1996), 181-184.
[22]G. Bacso, Zs. Tuza, Clique-transversal sets and weak 2-coloringsin graphs of small maximum degree, Discrete Mathematics and Theoretical Computer Sci-ence 11 (2) (2009),15-24.
[23]M.S. Chang, Y.H. Chen, G. J. Chang and J. H. Yan, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, Discret Appl. Math.66 (1996),189-203.
[24]L.H. Clark and R.C. Entringer, The number of cut vertices in graphs with given minimum degree, Discrete Math.18 (1990),137-145.
[25]G.J. Chang, M. Farber and Zs. Tuza, Algorithmic aspects of neighbourhood numbers, SIAM J. Discrete Math.6 (1993),24-29.
[26]G.J. Chang, M.J. Jou, The number of maximal independent sets in connected triangle-free graphs, Discrete Math.197/198 (1999),169-178.
[27]M.S. Chang, T. Kloks and C.M. Lee, Maximum clique transversals, In:Pro-ceedings of the 27th international workshop on graph-theoretic concepts in com-puter science. Lecture notes in computer science 2204 (2001),32-43.
[28]G. Chartrand, S.F. Kapoor, L. Lesniak, and S. Schuster, Near 1-factors in graphs, Proc. Fourteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, Congress Numerantium 41 (1984),131-147.
[29]G. Chartrand and L. Lesniak, Graphs and Digraphs,2nd Edition, Wadsworth and Brooks/Cole, Monterey, California,1986.
[30]J.E. Dunbar, S.T. Hedetniemi, M.A. Henning, and P. J. Slater, Signed dom-ination in graphs, in Graph Theory, Combinatorics, and Applications, John Wiley and Sons, Inc.1 (1995),311-322.
[31]G. Duran, M.C. Lin, S. Mera, J.L. Szwarcfter, Algorithms for finding clique-transversals of graphs, Annals of Operations Research 157 (2008),37-45.
[32]G. Duran, M.C. Lin and J.L. Szwarcfter, On clique-transversals and clique-independent sets, Annals of Operations Research 116 (2002),71-77.
[33]E. Dahlhaus, P.D. Mannuel and M. Mill, Maximum h-colourable subgraph problem in balanced graphs, Inform. Process. Lett.65 (1998),301-303.
[34]P. Erdos, T. Gallai and Zs. Tuza, Covering the cliques of a graph with vertices, Discrete Math.108 (1992),279-289.
[35]S. Fajtlowicz, The independence ratio for cubic graphs, Congr. Numer.19 (1977),273-277. [Proceedings of the Eighth Southeastern on Combinatorics, Graph Theory and Computing, Baton Rouge].
[36]S. Fajtlowicz, On the size of independent sets in graphs, Congr. Numer.21 (1978),269-274.
[37]K.L. Fraughnaugh, Independence in graphs with maximum degree four, J. Combin. Theory Ser. B 37 (1984),254-269.
[38]K.L. Fraughnaugh, Size and independence in triangle-free graphs with maxi-mum degree three, J. Graph Theory 14 (1990),525-535.
[39]R.J. Faudree, R.J. Gould, M.S. Jacobson, L.M. Lesniak and T.E. Lindquester, On independent generalized degrees and independence numbers in K(1, m)-free graphs, Discrete Math.103 (1992),17-24.
[40]K.L. Fraughnaugh and S.C. Locke, 11/30(finding large independent sets in connected triangle-free 3-regular graphs), J. Combin. Theory Ser. B 65 (1995), 51-72.
[41]K.L. Fraughnaugh and S.C. Locke, Finding independent sets in triangle-free graphs, SIAM J. Discrete Math.9 (1996),674-681.
[42]T. Gallai, Uber extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest, Eotvos Sect. Math.2 (1959),133-138.
[43]J.R. Griggs and C.M. Grinstead, D.R. Guichard, The number of maximal independent sets in a connected graph, Discrete Math.68 (1988),211-220.
[44]W. Goddard and M. A. Henning, Domination in planar graphs with small diameter, J. Graph Theory 40 (2002),1-25.
[45]J.R. Griggs and O. Murphy, Edge density and independence ratio in triangle-free graphs with maximum degree three, Discrete Math.152 (1996),157-170.
[46]V. Guruswami, C.P. Rangan, Algorithmic aspects of clique-transvsal and clique-independent sets, Discrete Appl. Math.100 (2000),183-202.
[47]C.C. Heckman, On the tightness of the 5/14 independence ratio, Discrete Math.308 (2008),3169-3179.
[48]J. Harant, A lower bound on the independence number of a graph, Discrete Math.188 (1998),139-243.
[49]J. Harant, M.A. Henning, D. Rautenbach, I. Schiermeyer, The independence number in graphs of maximum degree three, Discrete Math.308 (2008),5829-5833.
[50]M.A. Henning, L.Y. Kang, E.F. Shan, A. Yeo, On matching and total domi-nation in graphs, Discrete Math.308 (2008),2313-2318.
[51]J. Harant, I. Schiermeyer, On the independence number of a graph in terms of order and size, Discrete Math.232 (2001),131-138.
[52]A.M. Hobbs, E. Schmeichel, On the maximum number of independent edges in cubic graphs, Discrete Math.42 (1982),317-320.
[53]C.C. Heckman, R. Thomas, A new proof of the independence ratio of triangle-free cubic graphs, Discrete Math.233 (2001),233-237.
[54]C.C. Heckman, R. Thomas, Independent sets in triangle-free cubic planar graphs, J. Combin. Theory, Ser. B 96 (2006),253-275.
[55]M.A. Henning and A. Yeo, Tight lower bounds on the size of a maximum matching in a regular graph, Graphs and Combinatorics.23 (2007),647-657.
[56]K.F. Jones, Size and independence in triangle-free graphs with maximum de-gree three, J. Graph Theory 14(5) (1990),525-535.
[57]D.L. Kreher and S.P. Radziszowski, Minimum triangle-free graphs, Ars Com-binatoria 31 (1991),65-92.
[58]S.C. Locke, Bipartite density and the independence ratio, J. Graph Theory 10 (1986),47-53.
[59]C.M. Lee, Variations of maximum-clique transversal sets on graphs, Annals of Operations Research 181 (1) (2010),21-66.
[60]C.M. Lee, M.S. Chang, Distance-hereditary graphs are clique-perfect, Discrete Appl. Math.154 (2006),525-536.
[61]C.M. Lee, M.S.Chang, Signed and minus clique-transversal functions on graphs, Inform. Process. Lett.109 (2009),414-417.
[62]S.C. Locke, F. Lou, Finding independent sets in K4-hee 4-regular connected graphs, J. Combin. Theory, Ser. B 71 (1997),85-110.
[63]L. Lovasz and M.D. Plummer, Matching Theory, Ann. Discrete Math.29 (1986).
[64]P.S. Loh, B. Sudakov, Independent transversals in locally sparse graphs, J. Combin. Theory, Ser. B 97 (2007),904--918.
[65]Z.S. Liang, E.F. Shan, T.C.E. Cheng, Clique-transversal sets in cubic graphs. In Chen, B., Paterson, M., Zhang, G. (Eds.):ESCAPE 2007, Lecture Notes in Comput. Sci.,4614, Springer-Verlag,107-115 (2007)
[66]J. Lehel and Z. Tuza, Neighborhood perfect graphs, Discrete Math.61 (1986), 93-101.
[67]H. Li and C. Virlouvet, Neighborhood conditions for claw-free hamiltonian graphs, Ars Combin.29A (1990),109-116.
[68]S.A. Lakshmanan, A. Vijayakumar, The< t>-property of some classes of graphs, Discrete Math.309(2009),259-263.
[69]A. Nirmala and A.R. Rao, On the number of cut edges in a regular graph, Australasian Journal of Combinatorics 27 (2003),5-12.
[70]K. Nirmala and A.R. Rao, The number of cut vertices in a regular graph, Cahiers Centre Etudes Reserche Oper.17 (1975),295-299.
[71]Suil O and D.B. West, Matching and edge-connectivity in regular graphs, European Journal of Combinatorics 32 (2011),324-329.
[72]Suil O, D.B. West, Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree, J. Graph Theory 64 (2010),116-131.
[73]J. Petersen, Die theorie der regularen graph. Acta Math.15 (1891),193-220.
[74]M.D. Plummer, Extending matchings in claw-free graphs, Discrete Math.125 (1994),301-307.
[75]A.R. Rao, An extremal problem in graph theory, Israel J. Math.6 (1968), 261-266.
[76]A.R. Rao, Some extremal problems and characterizations in the theory of graphs, Ph. D. Thesis, Indian Statistical Institute (1969).
[77]S.B. Rao, Contributions to the theory of directed and undirected graphs, Ph. D. Thesis, Indian Statistical Institute (1970).
[78]D. Rautenbach, On vertex orderings and the stability number in triangle-free graphs, Discrete Math.231 (2001),411-420.
[79]Z. Ryjacek, I. Schiermeyer, On the independence number in-K1,r+1-free graphs, Discrete Math.138 (1995),365-374.
[80]W. Staton, Some Ramsey-type numbers and the independence ratio, Trans. Amer. Math. Soc.256 (1979),353-370.
[81]E.F. Shan, T.C.E. Cheng and L.Y. Kang, Bounds on the clique-transversal number of regular graphs, Science in China A:Mathematics 51 (5) (2008), 851-863.
[82]E.F. Shan, L.Y. Kang, Clique-transversal sets in 4-regular claw-free graphs, Acta Mathematica Sinica 27 (2011),883-890.
[83]E.F. Shan, H.C. Wang, Claw-free cubic graphs with clique-transversal number one-half their order, Appl. math. lett.24(7) 2011,1080-1083.
[84]Zs. Tuza, Covering all cliques of a graph, Discrete Math.86 (1990),117-126.
[85]W.T. Tutte, Connectivity in Graphs, University of Toronto Press, Toronto, 1966.
[86]H.C. Wang, L.Y. Kang, E.F. Shan, Signed clique-transversal functions in graphs, Int. J. Comput. math.87(11) (2010),2398-2407.
[87]徐保根,关于图的团符号控制数,系统科学与数学,28(2008),282-287.
[88]G.J. Xu, E.F. Shan, L.Y. Kang, T.C.E. Cheng, The algorithmic complexity of the minus clique-transversal problem, Appl. Math, and Computation 189 (2007),1410-1418.
[89]R. Yuster, Finding and counting cliques and independent sets in r-uniform hypergraphs, Inform. Process. Lett.99 (2006),130-134.
[90]R. Zenklusen, B. Ries, C. Picouleau, D. de Werra, M.-C. Costa, C. Bentz, Blockers and transversals, Discrete Math.309 (2009),4306-4314.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |