On well-covered graphs of odd girth 7 or greater

Bert Randerath; Preben Dahl Vestergaard

Discussiones Mathematicae Graph Theory (2002)

  • Volume: 22, Issue: 1, page 159-172
  • ISSN: 2083-5892

Abstract

top
A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [14] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. One of the most challenging problems in this area, posed in the survey of Plummer [15], is to find a good characterization of well-covered graphs of girth 4. We examine several subclasses of well-covered graphs of girth ≥ 4 with respect to the odd girth of the graph. We prove that every isolate-vertex-free well-covered graph G containing neither C₃, C₅ nor C₇ as a subgraph is even very well-covered. Here, a isolate-vertex-free well-covered graph G is called very well-covered, if G satisfies α(G) = n/2. A vertex set D of G is dominating if every vertex not in D is adjacent to some vertex in D. The domination number γ(G) is the minimum order of a dominating set of G. Obviously, the inequality γ(G) ≤ α(G) holds. The family γ = α of graphs G with γ(G) = α(G) forms a subclass of well-covered graphs. We prove that every connected member G of γ = α containing neither C₃ nor C₅ as a subgraph is a K₁, C₄,C₇ or a corona graph.

How to cite

top

Bert Randerath, and Preben Dahl Vestergaard. "On well-covered graphs of odd girth 7 or greater." Discussiones Mathematicae Graph Theory 22.1 (2002): 159-172. <http://eudml.org/doc/270191>.

@article{BertRanderath2002,
abstract = {A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [14] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. One of the most challenging problems in this area, posed in the survey of Plummer [15], is to find a good characterization of well-covered graphs of girth 4. We examine several subclasses of well-covered graphs of girth ≥ 4 with respect to the odd girth of the graph. We prove that every isolate-vertex-free well-covered graph G containing neither C₃, C₅ nor C₇ as a subgraph is even very well-covered. Here, a isolate-vertex-free well-covered graph G is called very well-covered, if G satisfies α(G) = n/2. A vertex set D of G is dominating if every vertex not in D is adjacent to some vertex in D. The domination number γ(G) is the minimum order of a dominating set of G. Obviously, the inequality γ(G) ≤ α(G) holds. The family $_\{γ=α\}$ of graphs G with γ(G) = α(G) forms a subclass of well-covered graphs. We prove that every connected member G of $_\{γ=α\}$ containing neither C₃ nor C₅ as a subgraph is a K₁, C₄,C₇ or a corona graph.},
author = {Bert Randerath, Preben Dahl Vestergaard},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {well-covered; independence number; domination number; odd girth; well-covered graphs},
language = {eng},
number = {1},
pages = {159-172},
title = {On well-covered graphs of odd girth 7 or greater},
url = {http://eudml.org/doc/270191},
volume = {22},
year = {2002},
}

TY - JOUR
AU - Bert Randerath
AU - Preben Dahl Vestergaard
TI - On well-covered graphs of odd girth 7 or greater
JO - Discussiones Mathematicae Graph Theory
PY - 2002
VL - 22
IS - 1
SP - 159
EP - 172
AB - A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [14] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. One of the most challenging problems in this area, posed in the survey of Plummer [15], is to find a good characterization of well-covered graphs of girth 4. We examine several subclasses of well-covered graphs of girth ≥ 4 with respect to the odd girth of the graph. We prove that every isolate-vertex-free well-covered graph G containing neither C₃, C₅ nor C₇ as a subgraph is even very well-covered. Here, a isolate-vertex-free well-covered graph G is called very well-covered, if G satisfies α(G) = n/2. A vertex set D of G is dominating if every vertex not in D is adjacent to some vertex in D. The domination number γ(G) is the minimum order of a dominating set of G. Obviously, the inequality γ(G) ≤ α(G) holds. The family $_{γ=α}$ of graphs G with γ(G) = α(G) forms a subclass of well-covered graphs. We prove that every connected member G of $_{γ=α}$ containing neither C₃ nor C₅ as a subgraph is a K₁, C₄,C₇ or a corona graph.
LA - eng
KW - well-covered; independence number; domination number; odd girth; well-covered graphs
UR - http://eudml.org/doc/270191
ER -

References

top
  1. [1] M.O. Albertson, L. Chan and R. Haas, Independence and graph homomorphisms, J. Graph Theory 17 (1993) 581-588, doi: 10.1002/jgt.3190170503. Zbl0781.05028
  2. [2] X. Baogen, E. Cockayne, T.W. Haynes, S.T. Hedetniemi and Z. Shangchao, Extremal graphs for inequalities involving domination parameters, Discrete Math. 216 (2000) 1-10, doi: 10.1016/S0012-365X(99)00251-4. Zbl0954.05037
  3. [3] C. Berge, Regularizable graphs, Ann. Discrete Math. 3 (1978) 11-19, doi: 10.1016/S0167-5060(08)70493-X. 
  4. [4] V. Chvátal and P.J. Slater, A note on well-covered graphs, Ann. Discrete Math. 55 (1993) 179-182, doi: 10.1016/S0167-5060(08)70387-X. Zbl0801.68119
  5. [5] O. Favaron, Very well-covered graphs, Discrete Math. 42 (1982) 177-187, doi: 10.1016/0012-365X(82)90215-1. Zbl0507.05053
  6. [6] A. Finbow and B. Hartnell, A game related to covering by stars, Ars Combin. 16 (A) (1983) 189-198. 
  7. [7] A. Finbow, B. Hartnell and R.J. Nowakowski, A characterization of well-covered graphs of girth 5 or greater, J. Combin. Theory (B) 57 (1993) 44-68, doi: 10.1006/jctb.1993.1005. Zbl0777.05088
  8. [8] A. Finbow, B. Hartnell and R.J. Nowakowski, A characterization of well-covered graphs which contain neither 4- nor 5-cycles, J. Graph Theory 18 (1994) 713-721, doi: 10.1002/jgt.3190180707. Zbl0810.05058
  9. [9] J.F. Fink, M.S. Jacobson, L.F. Kinch and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (1985) 287-293, doi: 10.1007/BF01848079. Zbl0602.05043
  10. [10] O. Ore, Theory of Graphs (Amer. Math. Soc. Colloq. Publ. 38, 1962). 
  11. [11] C. Payan and N.H. Xuong, Domination-balanced graphs. J. Graph Theory 6 (1982) 23-32, doi: 10.1002/jgt.3190060104. Zbl0489.05049
  12. [12] M.R. Pinter, A class of planar well-covered graphs with girth four, J. Graph Theory 19 (1995) 69-81, doi: 10.1002/jgt.3190190108. Zbl0813.05054
  13. [13] M.R. Pinter, A class of well-covered graphs with girth four, Ars Combin. 45 (1997) 241-255. Zbl0933.05119
  14. [14] M.D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91-98, doi: 10.1016/S0021-9800(70)80011-4. Zbl0195.25801
  15. [15] M.D. Plummer, Well-covered graphs: a survey, Quaestiones Math. 16 (1993) 253-287, doi: 10.1080/16073606.1993.9631737. Zbl0817.05068
  16. [16] B. Randerath and L. Volkmann, Characterization of graphs with equal domination and covering number, Discrete Math. 191 (1998) 159-169, doi: 10.1016/S0012-365X(98)00103-4. Zbl0955.05088
  17. [17] R.S. Sankaranarayanan and L.K. Stewart, Complexity results for well-covered graphs, Networks 22 (1992) 247-262, doi: 10.1002/net.3230220304. Zbl0780.90104
  18. [18] J. Staples, Ph. D. dissertation (Vanderbilt University, Nashville, TN, 1975). 
  19. [19] L. Szamkołowicz, Sur la classification des graphes en vue des propriétés de leurs noyaux, Prace Nauk. Inst. Mat. i Fiz. Teoret., Politechn. Wrocław., Ser. Stud. Mater. 3 (1970) 15-21. Zbl0264.05125
  20. [20] J. Topp and L. Volkmann, On domination and independence numbers of graphs, Resultate Math. 17 (1990) 333-341. Zbl0748.05066
  21. [21] W.T. Tutte, The 1-factors of oriented graphs, Proc. Amer. Math. Soc. 4 (1953) 922-931. Zbl0052.20004

NotesEmbed ?

top

You must be logged in to post comments.