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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.