Article in volume
Authors:
Title:
Characterization of $\alpha$-excellent $2$-trees
PDFSource:
Discussiones Mathematicae Graph Theory 45(1) (2025) 67-80
Received: 2022-12-31 , Revised: 2023-08-28 , Accepted: 2023-08-29 , Available online: 2023-10-03 , https://doi.org/10.7151/dmgt.2520
Abstract:
A graph is $\alpha$-excellent if every vertex of the graph is contained in some
maximum independent set of the graph. In this paper, we present two
characterizations of the $\alpha$-excellent $2$-trees.
Keywords:
independence number, excellent graph, $k$-tree
References:
- C. Berge, The theory of Graphs and its Applications (Methuen, London, 1962).
- C. Berge, Some common properties for regularizable graphs, edge-critical graphs and $B$-graphs, in: Graph Theory and Algorithms, N. Saito, T. Nishiezeki (Ed(s)), Lecture Notes in Comput. Sci. 108, (Springer, Berlin, Heidelberg 1981) 108–123.
https://doi.org/10.1007/3-540-10704-5_10 - C. Berge, Graphs (North-Holland, Amsterdam, 1985).
- M. Dettlaff, M.A. Henning and J. Topp, On $\alpha$-excellent graphs, Bull. Malays. Math. Sci. Soc. 46 (2023) 65.
https://doi.org/10.1007/s40840-022-01456-0 - M. Dettlaff, M. Lemańska and J. Topp, Common independence in graphs, Symmetry 13(8) (2021) 1411.
https://doi.org/10.3390/sym13081411 - G.S. Domke, J.H. Hattingh and L.R. Markus, On weakly connected domination in graphs II, Discrete Math. 305 (2005) 112–122.
https://doi.org/10.1016/j.disc.2005.10.006 - G.H. Fricke, T.W. Haynes, S.M. Hedetniemi, S.T. Hedetniemi and R.C. Laskar, Excellent trees, Bull. Inst. Combin. Appl. 34 (2002) 27–38.
- W. Goddard and M.A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313 (2013) 839–854.
https://doi.org/10.1016/j.disc.2012.11.031 - T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Topics in Domination in Graphs, Dev. Math. 64 (Springer, Cham, 2020).
https://doi.org/10.1007/978-3-030-51117-3 - T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Structures of Domination in Graphs, Dev. Math. 66 (Springer, Cham, 2021).
https://doi.org/10.1007/978-3-030-58892-2 - T.W. Haynes, S.T. Hedetniemi and M.A. Henning, Domination in Graphs: Core Concepts, Springer Monogr. Math. (Springer, Cham, 2023).
https://doi.org/10.1007/978-3-031-09496-5 - O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ. 38 (Providence, RI, 1962).
- M.D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91–98.
https://doi.org/10.1016/S0021-9800(70)80011-4 - M.D. Plummer, Well-covered graphs: a survey, Quaest. Math. 16 (1993) 253–287.
https://doi.org/10.1080/16073606.1993.9631737 - A.P. Pushpalatha, G. Jothilakshmi, S. Suganthi and V. Swaminathan, $\beta_0$-excellent graphs, Int. J. Contemp. Math. Sci. 6 (2011) 1447–1451.
- A.P. Pushpalatha, G. Jothilakshmi, S. Suganthi and V. Swaminathan, Very $\beta_0$-excellent graphs, Taga Journal 14 (2018) 144–148.
- D.J. Rose, On simple characterizations of $k$-trees, Discrete Math. 7 (1974) 317–322.
https://doi.org/10.1016/0012-365X(74)90042-9 - J. Topp, Domination, Independence and Irredundance in Graphs, Dissertationes Math. 342 (Institute of Mathematics, Polish Academy of Sciences, Warsaw, 1995).
Close