On well-covered Cartesian products

DOI10.1007/S00373-018-1943-3MaRDI QIDQ1756093zbMATH OpenOpenAlexFDO

Authors Bert L. Hartnell, Douglas F. Rall, Kirsti Wash

Publication date 11 January 2019

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.08716

zbMATH Keywords

1-well-coveredCartesian productisolatable vertexwell-covered graph

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Abstract: In 1970, Plummer defined a well-covered graph to be a graph $G$ in which all maximal independent sets are in fact maximum. Later Hartnell and Rall showed that if the Cartesian product $GBoxH$ is well-covered, then at least one of $G$ or $H$ is well-covered. In this paper, we consider the problem of classifying all well-covered Cartesian products. In particular, we show that if the Cartesian product of two nontrivial, connected graphs of girth at least $4$ is well-covered, then at least one of the graphs is $K_2$. Moreover, we show that $K_{2}Box{K}_2$ and $C_{5}Box{K}_2$ are the only well-covered Cartesian products of nontrivial, connected graphs of girth at least $5$.

Recommendations

• On the well-coveredness of Cartesian products of graphs
• On the Cartesian product of non well-covered graphs
• On well-covered direct products
• scientific article; zbMATH DE number 68351
• A characterization of well covered graphs of girth 5 or greater

Cites work

• A characterization of well covered graphs of girth 5 or greater
• A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
• scientific article; zbMATH DE number 68351 (Why is no real title available?)
• scientific article; zbMATH DE number 1286748 (Why is no real title available?)
• scientific article; zbMATH DE number 205349 (Why is no real title available?)
• scientific article; zbMATH DE number 1409193 (Why is no real title available?)
• scientific article; zbMATH DE number 3892971 (Why is no real title available?)
• On 1-well-covered graphs
• On the Cartesian product of non well-covered graphs
• On the well-coveredness of Cartesian products of graphs
• Some covering concepts in graphs
• WELL-COVERED GRAPHS: A SURVEY

Cited in

(12)

• On Cartesian products of orthogonal double covers
• On the Cartesian product of non well-covered graphs
• On well-dominated direct, Cartesian and strong product graphs
• On well-covered direct products
• Well-hued graphs
• On well-dominated graphs
• scientific article; zbMATH DE number 68351 (Why is no real title available?)
• The well-covered dimension of products of graphs
• scientific article; zbMATH DE number 2119455 (Why is no real title available?)
• On expressible sets of products
• A characterization of well-dominated Cartesian products
• On the well-coveredness of Cartesian products of graphs

This page was built for publication: On well-covered Cartesian products

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1756093)