The Well-Covered Dimension Of Products Of Graphs

• Autorzy: Isaac Birnbaum , Megan Kuneli , Robyn McDonald , Katherine Urabe , Oscar Vega
• Języki publikacji: EN

Abstrakty

EN

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 Kn × 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.

Słowa kluczowe

EN

well-covered dimension; maximal independent sets.

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 4
• Strony: 811-827

Daty

wydano

2014-11-01

otrzymano

2012-12-13

poprawiono

2013-11-19

zaakceptowano

2013-11-19

online

2014-11-15

Twórcy

autor

Isaac Birnbaum

• Department of Mathematics California State University, Fresno Fresno, CA, USA

autor

Megan Kuneli

• Department of Mathematics California State University, Fresno Fresno, CA, USA

autor

Robyn McDonald

• California State University, Stanislaus Turlock, CA, USA

autor

Katherine Urabe

• Department of Mathematics California State University, Fresno Fresno, CA, USA

autor

Oscar Vega

• Department of Mathematics California State University, Fresno Fresno, CA, USA

Bibliografia

• [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
• [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
• [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
• [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
• [5] M.D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91-98. doi:10.1016/S0021-9800(70)80011-4
• [6] D.B. West, Introduction to Graph Theory, Second Edition (Prentice Hall, Upper Saddle River, 2001).

Identyfikatory

DOI

10.7151/dmgt.1770