Artículos de revistas
Recognizing Well Covered Graphs Of Families With Special P4-components
Registro en:
Graphs And Combinatorics. , v. 29, n. 3, p. 553 - 567, 2013.
9110119
10.1007/s00373-011-1123-1
2-s2.0-84877615612
Autor
Klein S.
de Mello C.P.
Morgana A.
Institución
Resumen
A graph G is called well covered if every two maximal independent sets of G have the same number of vertices. In this paper we shall use the modular and primeval decomposition techniques to decide well coveredness of graphs such that, either all their P4-connected components (in short, P4-components) are separable or they belong to well known classes of graphs that, in some local sense, contain few P4's. In particular, we shall consider the class of cographs, P4-reducible, P4-sparse, extended P4-reducible, extended P4-sparse graphs, P4-extendible graphs, P4-lite graphs, and P4-tidy graphs. © 2011 Springer. 29 3 553 567 Baumann, S., (1996) A linear algorithm for the homogeneous decomposition of graphs, , Report No. M-9615, Zentrum Mathematik, Technische Universität München Caro, Y., Subdivisions, parity and well-covered graphs (1997) J. Graph Theory, 25, pp. 85-94 Caro, Y., Sebö, A., Tarsi, M., Recognizing greedy structures (1996) J. Algorithms, 20, pp. 137-156 Chvátal, V., Slater, P.J., A note on well-covered graphs (1993) Ann. Discrete Math., 55, pp. 179-182 Corneil, D.G., Lerchs, H., Stewart Burlingham, L., Complement reducible graphs (1981) Discrete Appl. Math., 3, pp. 163-174 Corneil, D.G., Perl, Y., Stewart, L.K., Cographs: recognition, applications and algorithms (1984) Congressus Numerantium, 43, pp. 249-258 Dean, N., Zito, J., Well covered graphs and extendability (1994) Discrete Math., 126, pp. 67-80 Fradkin, A.O., On the well-coveredness of Cartesian products of graphs (2009) Discrete Math., 309 (1), pp. 238-246 Finbow, A., Hartnell, B., Nowakowski, R., A characterization of well-covered graphs of girth 5 or greater (1993) J. Combin. Theory B, 57, pp. 44-68 Giakoumakis, V., Vanherpe, J.-M., On extended P4-reducible and extended P4-sparse graphs (1997) Theor. Comput. Sci., 180, pp. 269-286 Giakoumakis, V., Roussel, F., Thuillier, H., On P4-tidy graphs (1997) Discrete Math. Theor. Comput. Sci., 1, pp. 17-41 Hammer, P.L., Simeone, B., The splittance of a graph (1981) Combinatorica, 1, pp. 275-284 Hóang, C., (1985) Doctoral Dissertation, , McGill University, Montreal Jamison, B., Olariu, S., A new class of brittle graphs (1989) Stud. Appl. Math., 81, pp. 89-92 Jamison, B., Olariu, S., P4-reducible graphs, a class of uniquely tree representable graphs (1989) Stud. Appl. Math., 81, pp. 79-87 Jamison, B., Olariu, S., On a unique tree representation for P4-extendible graphs (1991) Discrete Appl. Math., 34, pp. 151-164 Jamison, B., Olariu, S., A unique tree representation for P4-sparse graphs (1992) Discrete Appl. Math., 35, pp. 115-129 Jamison, B., Olariu, S., p-Components and the homogeneous decomposition of graphs (1995) SIAM J. Discrete Math., 8, pp. 448-463 McConnell, R.M., Spinrad, J.P., Modular decomposition and transitive orientation (1999) Discrete Math., 201, pp. 189-241 Prisner, B., Topp, J., Vestergaard, P.D., Well covered simplicial, chordal, and circular arc graphs (1996) J. Graph Theory, 21 (2), pp. 113-119 Plummer, M.D., Some covering concepts in graphs (1970) J. Combin. Theory, 8, pp. 91-98 Plummer, M.D., Well covered graphs: a survey (1993) Quaestiones Math., 16, pp. 253-287 Randerath, B., Vestergaard, P.D., Well covered graphs and factors (2006) Discrete Appl. Math., 154, pp. 1416-1428 Sankaranarayana, R.S., Stewart, L.K., Complexity results for well-covered graphs (1992) Networks, 22, pp. 247-262 Tankus, D., Tarsi, M., The structure of well covered graphs and the complexity of their recognition problems (1997) J. Combin. Theory B, 69, pp. 230-233 Tedder, M., Corneil, D.G., Habib, M., Paul, C., (2007) Simple, linear-time modular decomposition, , CoRR abs/0710. 3901