1-well-covered graphs containing a clique of size n∕3
Abstract
A graph is well-covered if all of its maximal independent sets have the same size. A graph that remains well-covered upon the removal of any vertex is called a 1-well-covered graph. These graphs, when they have no isolated vertices, are also known as W2 graphs. It is well-known that every graph G ∈ W2 has two disjoint maximum independent sets. In this paper, we investigate connected W2 graphs with n vertices that contain a clique of size n∕3. We prove that if the removal of two disjoint maximum independent sets from a graph G ∈ W2 leaves a clique of size at least 3, then G contains a clique of size n∕3. Using this result, we provide a complete characterization of these graphs, based on eleven graph families.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2024.12.2.8
References
C. Berge. Some common properties for regularizable graphs, edge-critical graphs and b-graphs. In Graph Theory and Algorithms, Springer, (1981), 108-123.
T. Biyikoglu and Y. Civan. Vertex-decomposable graphs, codismantlability, Cohen-Macaulayness, and Castelnuovo-Mumford regularity. The Electronic Journal of Combinatorics, (2014), P1-1.
S. Campbell, M. Ellingham, and G. Royle. A characterization of well-covered cubic graphs. Journal of Combinatorial Computing, 13, (1993), 193-212.
V. Chvatal and P. J. Slater. A note on well-covered graphs. In Annals of Discrete Mathematics, 55, (1993), 179-181.
M. Demange and T. Ekim. Efficient recognition of equimatchable graphs. Information Processing Letters, 114(1-2) (2014), 66-71.
Z. Deniz. A classication of 1-well-covered graphs. Turkish Journal of Mathematics, 45, (2021), 2817-2829.
Z. Deniz and T. Ekim. Edge-stable equimatchable graphs. Discrete Applied Mathematics, 261, (2019), 136-147.
O. Favaron. Very well covered graphs. Discrete Mathematics, 42(2-3) (1982), 177-187.
A. S. Finbow, B. L. Hartnell, and R. J. Nowakowski. A characterization of well covered graphs of girth 5 or greater. Journal of Combinatorial Theory, Series B, 57(1), (1993), 44-68.
A. S. Finbow, B. L. Hartnell, and R. J. Nowakowski. A characterization of well-covered graphs that contain neither 4-nor 5-cycles. Journal of Graph Theory, 18(7), (1994), 713-721.
A. S. Finbow, B. L. Hartnell, and M. D. Plummer. On the structure of 4-regular planar well-covered graphs. Discrete Applied Mathematics, 283, (2020), 655-688.
B. Hartnell. A characterization of the 1-well-covered graphs with no 4-cycles. In Graph Theory in Paris, Springer, (2006) 219-224.
D. T. Hoang and T. N. Trung. A characterization of triangle-dominating graphs in W2 and applications. arXiv preprint arXiv:1606.02815, (2016).
V. E. Levit and E. Mandrescu. 1-well-covered graphs revisited. European Journal of Combinatorics, 80 (2019), 261-272.
M. P. Pinter. Planar regular one-well-covered graphs. Technical report, Vanderbilt University Nashville TN, (1991).
M. R. Pinter. W2 graphs and strongly well-covered graphs: Two well-covered graph subclasses. Phd thesis, Vanderbilt University, (1992).
M. R. Pinter. A class of planar well-covered graphs with girth four. Journal of Graph Theory, 19(1), (1995), 69-81.
M. R. Pinter. A class of well-covered graphs with girth four. Ars Combinatoria, 45, (1997), 241-255.
R. S. Sankaranarayana and L. K. Stewart. Complexity results for well-covered graphs. Networks, 22(3), (1992), 247-262.
J. A. W. Staples. On some subclasses of well-covered graphs. Journal of Graph Theory, 3(2), (1979), 197-204.
R. Woodroofe. Vertex decomposable graphs and obstructions to shellability. Proceedings of the American Mathematical Society, 137(10), (2009), 3235-3246.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.