×

The well-covered dimension of products of graphs. (English) Zbl 1303.05164

Summary: We discuss how to find the well-covered dimension of a graph that is the Cartesian product of paths, cycles, complete graphs, and other simple graphs. Also, a bound for the well-covered dimension of \(K_n\times G\) is found, provided that \(G\) has a largest greedy independent decomposition of length \(c < n\). Formulae to find the well-covered dimension of graphs obtained by vertex blowups on a known graph, and to the lexicographic product of two known graphs are also given.

MSC:

05C76 Graph operations (line graphs, products, etc.)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C35 Extremal problems in graph theory
15A03 Vector spaces, linear dependence, rank, lineability
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J.I. Brown and R.J. Nowakowski, Well-covered vector spaces of graphs, SIAM J. Discrete Math. 19 (2005) 952-965. doi:10.1137/S0895480101393039; · Zbl 1104.05052
[2] Y. Caro, M.N. Ellingham and J.E. Ramey, Local structure when all maximal inde- pendent sets have equal weight , SIAM J. Discrete Math. 11 (1998) 644-654. doi:10.1137/S0895480196300479; · Zbl 0914.05061
[3] Y. Caro and R. Yuster, The uniformity space of hypergraphs and its applications, Discrete Math. 202 (1999) 1-19. doi:10.1016/S0012-365X(98)00344-6; · Zbl 0932.05069
[4] A. Ovetsky, On the well-coveredness of Cartesian products of graphs, Discrete Math. 309 (2009) 238-246. doi:10.1016/j.disc.2007.12.083; · Zbl 1229.05239
[5] M.D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91-98. doi:10.1016/S0021-9800(70)80011-4; · Zbl 0195.25801
[6] D.B. West, Introduction to Graph Theory, Second Edition (Prentice Hall, Upper Saddle River, 2001).;
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.