On the Sizes of Maximal Independent Sets of Cylindrical Grid Graphs

Rommel Melgaço Barbosa, Márcia Rodrigues Cappelle

Abstract


If a graph G has exactly t different sizes of maximal independent sets, G belongs to a collection called Mt. For the Cartesian product of the graph Pn, the path of length n, and Cm, the cycle of length m, called cylindrical grid, we present a method to find maximal independent sets having different sizes and a lower bound on t, such that these graphs belong to Mt.


Full Text:

PDF

References


R. Barbosa & B.L. Hartnell. Some problems based on the relative sizes of the maximal independent sets in a graph. Congr. Numerantium, 131 (1998), 115–121.

R. Barbosa & B.L. Hartnell. The effect of vertex and edge deletion on the number of sizes of maximal independent sets. J. Combin. Math. Combin. Comput., 70 (2009), 111–116.

R. Barbosa, M.R. Cappelle & D. Rautenbach. On Graphs with Maximal Independents Sets of Few Sizes, Minimum Degree at least 2, and Girth at least 7. Discrete Math., 313 (2013), 1630–1635.

A. Finbow, B. Hartnell & C. Whitehead. A characterization of graphs of girth eight or more with exactly two sizes of maximal independent sets. Discrete Math., 125 (1994), 153–167.

A.O. Fradkin. On the well-coveredness of Cartesian products of graphs. Discrete Math., 309(1) (2009), 238–246.

B.L. Hartnell & D.F. Rall. On graphs having maximal independent sets of exactly t distinct cardinal- ities. Graphs and Combinatorics, 29(3) (2013), 519–525.

B.L. Hartnell & D.F. Rall. On the Cartesian product of non well-covered graphs. Eletr. J. Comb., 20(2) (2013), P21.

M. Nandi, S. Parui & A. Adhikari. The domination numbers of cylindrical grid graphs Applied Math. and Comp., 217(10) (2011), 4879–4889.

M.D. Plummer. Well-covered graphs, J. Combin. Theory, 8 (1970), 91–98.

M.D. Plummer. Well-covered graphs: a survey, Quaestiones Math., 16 (1993), 253–287.

J. Topp & L. Volkmann. On the well coveredness of Products of Graphs. Ars Combinatoria, 33 (1992), 199–215.




DOI: https://doi.org/10.5540/tema.2016.017.03.0367

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Trends in Computational and Applied Mathematics

A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)

 

Indexed in:

                       

         

 

Desenvolvido por:

Logomarca da Lepidus Tecnologia