A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles

DOI10.1002/jgt.3190180707zbMath0810.05058OpenAlexW2125478135MaRDI QIDQ4312248

Arthur S. Finbow, Bert L. Hartnell, Richard J. Nowakowski

Publication date: 4 April 1995

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.3190180707

zbMATH Keywords

cyclescharacterizationindependent setpolynomial timewell-covered graphextendable vertex

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Related Items (40)

Well-covered triangulations. IV ⋮ Complexity results for well‐covered graphs ⋮ The structure of well-covered graphs with no cycles of length 4 ⋮ \((C_3, C_4, C_5, C_7)\)-free almost well-dominated graphs ⋮ The well-covered dimension of random graphs ⋮ Well-dominated graphs without cycles of lengths 4 and 5 ⋮ Reconfiguring dominating sets in some well-covered and other classes of graphs ⋮ Equimatchable claw-free graphs ⋮ On 4-connected claw-free well-covered graphs ⋮ On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity ⋮ Using maximality and minimality conditions to construct inequality chains ⋮ A characterization of Zm-well-covered graphs of girth 6 or more ⋮ Extending Berge's and Favaron's results about well-covered graphs ⋮ Recognizing well-dominated graphs is coNP-complete ⋮ Recognizing generating subgraphs in graphs without cycles of lengths 6 and 7 ⋮ On the structure of 4-regular planar well-covered graphs ⋮ Weighted well-covered graphs without \(C_{4}, C_{5}, C_{6}, C_{7}\) ⋮ Computing well-covered vector spaces of graphs using modular decomposition ⋮ Well-covered graphs with constraints on \(\Delta\) and \(\delta\) ⋮ Three remarks on \(\mathbf{W}_{\mathbf{2}}\) graphs ⋮ On the probe problem for \((r,\ell )\)-well-coveredness ⋮ On relating edges in graphs without cycles of length 4 ⋮ Weighted well-covered claw-free graphs ⋮ Triangulations and equality in the domination chain ⋮ On vertex decomposable and Cohen-Macaulay regular graphs ⋮ On well-covered Cartesian products ⋮ On well-covered pentagonalizations of the plane ⋮ Well-covered graphs and factors ⋮ Complexity results for generating subgraphs ⋮ Weighted well-covered graphs without cycles of lengths 5, 6 and 7 ⋮ Unnamed Item ⋮ A characterization of well-covered graphs in terms of forbidden costable subgraphs ⋮ Cohen–Macaulay graphs with large girth ⋮ Recognizing Generating Subgraphs Revisited ⋮ Well-covered graphs without cycles of lengths 4, 5 and 6 ⋮ Well-covered graphs and extendability ⋮ Partitions and well-coveredness: the graph sandwich problem ⋮ Unmixedness of some weighted oriented graphs ⋮ A characterization of graphs of girth eight or more with exactly two sizes of maximal independent sets ⋮ On well-covered direct products

This page was built for publication: A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles