Navegar

Colección

Datos Estadísticas

Artículo

El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We initiate the study of graph classes of power-bounded clique-width, that is, graph classes for which there exist integers k and ℓ such that the kth powers of the graphs are of clique-width at most ℓ. We give sufficient and necessary conditions for this property. As our main results, we characterize graph classes of power-bounded clique-width within classes defined by either one forbidden induced subgraph, or by two connected forbidden induced subgraphs. We also show that for every positive integer k, there exists a graph class such that the kth powers of graphs in the class form a class of bounded clique-width, while this is not the case for any smaller power. © 2015 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Graph classes with and without powers of bounded clique-width
Autor:Bonomo, F.; Grippo, L.N.; Milanič, M.; Safe, M.D.
Filiación:Depto. de Computación, FCEyN, Universidad de Buenos Aires, Argentina
CONICET, Argentina
Instituto de Ciencias, Universidad Nacional de General Sarmiento, Los Polvorines, Argentina
Andrej Marušič Institute, University of Primorska, Muzejski trg 2, Koper, 6000, Slovenia
Faculty of Mathematics, Natural Sciences and Information Technologies, University of Primorska, Glagoljaška 8, Koper, 6000, Slovenia
Palabras clave:Clique-width; Hereditary graph class; Power of a graph; Power-bounded clique-width; Combinatorial mathematics; Clique-width; Forbidden induced subgraphs; Graph class; Induced subgraphs; Positive integers; Power of a graph; Sufficient and necessary condition; Within class; Graph theory
Año:2016
Volumen:199
Página de inicio:3
Página de fin:15
DOI: http://dx.doi.org/10.1016/j.dam.2015.06.010
Título revista:Discrete Applied Mathematics
Título revista abreviado:Discrete Appl Math
ISSN:0166218X
CODEN:DAMAD
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v199_n_p3_Bonomo

Referencias:

  • Alekseev, V.E., Lozin, V., Malyshev, D., Milanič, M., The maximum independent set problem in planar graphs (2008) Lecture Notes in Comput. Sci. Springer Berlin, 5162, pp. 96-107. , Mathematical Foundations of Computer Science 2008
  • Bodlaender, H.L., A partial k-arboretum of graphs with bounded treewidth (1998) Theoret. Comput. Sci., 209 (1-2), pp. 1-45
  • Boliac, R., Lozin, V., On the clique-width of graphs in hereditary classes (2002) Lecture Notes in Comput. Sci. Springer Berlin, 2518, pp. 44-54. , Algorithms and Computation
  • Brandstädt, A., Dragan, F.F., Xiang, Y., Yan, C., Generalized powers of graphs and their algorithmic use (2006) Lecture Notes in Comput. Sci. Springer Berlin, 4059, pp. 423-434. , Algorithm Theory - SWAT 2006
  • Brandstädt, A., Le, V.B., Spinrad, J.P., Graph classes: A survey (1999) SIAM Monographs on Discrete Mathematics and Applications, , Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA
  • Brandstädt, A., Leitert, A., Rautenbach, D., Efficient dominating and edge dominating sets for graphs and hypergraphs (2012) Lecture Notes in Computer Science Springer, 7676, pp. 267-277. , ISAAC K.-M. Chao, T. Sheng Hsu, D.-T. Lee
  • Brandstädt, A., Lozin, V.V., On the linear structure and clique-width of bipartite permutation graphs (2003) Ars Combin., 67, pp. 273-281
  • Chandran, L.S., Kavitha, T., The treewidth and pathwidth of hypercubes (2006) Discrete Math., 306 (3), pp. 359-365
  • Cicalese, F., Cordasco, G., Gargano, L., Milanič, M., Vaccaro, U., Latency-bounded target set selection in social networks (2014) Theoret. Comput. Sci., 535, pp. 1-15
  • Corneil, D.G., Habib, M., Lanlignel, J.-M., Reed, B., Rotics, U., Polynomial-time recognition of clique-width ≤3 graphs (2012) Discrete Appl. Math., 160 (6), pp. 834-865
  • Corneil, D.G., Rotics, U., On the relationship between clique-width and treewidth (2005) SIAM J. Comput., 34 (4), pp. 825-847. , electronic
  • Courcelle, B., Engelfriet, J., Rozenberg, G., Handle-rewriting hypergraph grammars (1993) J. Comput. System Sci., 46 (2), pp. 218-270
  • Courcelle, B., Makowsky, J.A., Rotics, U., Linear time solvable optimization problems on graphs of bounded clique-width (2000) Theory Comput. Syst., 33 (2), pp. 125-150
  • Courcelle, B., Olariu, S., Upper bounds to the clique width of graphs (2000) Discrete Appl. Math., 101 (1-3), pp. 77-114
  • Dabrowski, K.K., Huang, S., Paulusma, D., Bounding clique-width via perfect graphs (2015) Language and Automata Theory and Applications - 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings, pp. 676-688
  • Dabrowski, K., Paulusma, D., Clique-width of graph classes defined by two forbidden induced subgraphs (2015) Lecture Notes in Comput. Sci., 9079, pp. 167-181. , Algorithms and Complexity - 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015
  • Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S., Clique-width is NP-complete (2009) SIAM J. Discrete Math., 23 (2), pp. 909-939
  • Fischer, E., Makowsky, J.A., Ravve, E.V., Counting truth assignments of formulas of bounded tree-width or clique-width (2008) Discrete Appl. Math., 156 (4), pp. 511-529
  • Gallai, T., Transitiv orientierbare Graphen (1967) Acta Math. Acad. Sci. Hungar., 18, pp. 25-66
  • Gallai, T., A translation of T. Gallai's paper: "transitiv orientierbare Graphen (2001) Perfect Graphs, pp. 25-66. , Wiley-Intersci. Ser. Discrete Math. Optim. Wiley Chichester
  • (1967) Acta Math. Acad. Sci. Hungar., 18, pp. 25-66. , MR0221974 (36 #5026)
  • Gerber, M.U., Kobler, D., Algorithms for vertex-partitioning problems on graphs with fixed clique-width (2003) Theoret. Comput. Sci., 299 (1-3), pp. 719-734
  • Giménez, O., Hliněný, P., Noy, M., Computing the Tutte polynomial on graphs of bounded clique-width (2006) SIAM J. Discrete Math., 20 (4), pp. 932-946
  • Golumbic, M.C., Rotics, U., On the clique-width of some perfect graph classes (2000) Internat. J. Found. Comput. Sci., 11 (3), pp. 423-443
  • Gurski, F., Wanke, E., The tree-width of clique-width bounded graphs without Kn,n (2000) Lecture Notes in Comput. Sci., 1928, pp. 196-205. , Graph-Theoretic Concepts in Computer Science (Konstanz, 2000) Springer Berlin
  • Gurski, F., Wanke, E., Line graphs of bounded clique-width (2007) Discrete Math., 307 (22), pp. 2734-2754
  • Habib, M., Maurer, M.C., On the X-join decomposition for undirected graphs (1979) Discrete Appl. Math., 1 (3), pp. 201-207
  • Haynes, T.W., Hedetniemi, S.T., Slater, P.J., Domination in graphs (1998) Monographs and Textbooks in Pure and Applied Mathematics, 209. , Marcel Dekker Inc. New York
  • Heggernes, P., Meister, D., Rotics, U., Computing the clique-width of large path powers in linear time via a new characterisation of clique-width (2011) Lecture Notes in Comput. Sci., 6651, pp. 233-246. , Computer Science - Theory and Applications Springer Heidelberg
  • Hell, P., Huang, J., Interval bigraphs and circular arc graphs (2004) J. Graph Theory, 46 (4), pp. 313-327
  • Johansson, Ö., Clique-decomposition, NLC-decomposition, and modular decomposition - Relationships and results for random graphs (1998) Proceedings of the Twenty-ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing, 132, pp. 39-60. , Boca Raton, FL, 1998
  • Kamiński, M., Lozin, V.V., Milanič, M., Recent developments on graphs of bounded clique-width (2009) Discrete Appl. Math., 157 (12), pp. 2747-2761
  • Karpovsky, M.G., Chakrabarty, K., Levitin, L.B., On a new class of codes for identifying vertices in graphs (1998) IEEE Trans. Inform. Theory, 44 (2), pp. 599-611
  • Kobler, D., Rotics, U., Edge dominating set and colorings on graphs with fixed clique-width (2003) Discrete Appl. Math., 126 (2-3), pp. 197-221
  • Lin, M.C., Rautenbach, D., Soulignac, F.J., Szwarcfiter, J.L., Powers of cycles, powers of paths, and distance graphs (2011) Discrete Appl. Math., 159 (7), pp. 621-627
  • Lozin, V.V., Minimal classes of graphs of unbounded clique-width (2011) Ann. Comb., 15 (4), pp. 707-722
  • Lozin, V., Milanič, M., Tree-width and optimization in bounded degree graphs (2007) Lecture Notes in Comput. Sci., 4769, pp. 45-54. , Graph-Theoretic Concepts in Computer Science Springer Berlin
  • Lozin, V.V., Milanič, M., Critical properties of graphs of bounded clique-width (2013) Discrete Math., 313 (9), pp. 1035-1044
  • Lozin, V.V., Rautenbach, D., The tree- and clique-width of bipartite graphs in special classes (2006) Australas. J. Combin., 34, pp. 57-67
  • Makowsky, J.A., Rotics, U., On the clique-width of graphs with few P4's (1999) Internat. J. Found. Comput. Sci., 10 (3), pp. 329-348
  • Milanič, M., Hereditary efficiently dominatable graphs (2013) J. Graph Theory, 73 (4), pp. 400-424
  • Moonen, L.S., Spieksma, F.C.R., Exact algorithms for a loading problem with bounded clique width (2006) INFORMS J. Comput., 18 (4), pp. 455-465
  • Prisner, E., Graph dynamics (1995) Pitman Research Notes in Mathematics Series, 338. , Longman Harlow
  • Roberts, F.S., Indifference graphs (1969) Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), pp. 139-146. , Academic Press New York
  • Robertson, N., Seymour, P.D., Graph minors. II. Algorithmic aspects of tree-width (1986) J. Algorithms, 7 (3), pp. 309-322
  • Schoone, A.A., Bodlaender, H.L., Van Leeuwen, J., Diameter increase caused by edge deletion (1987) J. Graph Theory, 11 (3), pp. 409-427
  • Suchan, K., Todinca, I., On powers of graphs of bounded NLC-width (clique-width) (2007) Discrete Appl. Math., 155 (14), pp. 1885-1893
  • Todinca, I., Coloring powers of graphs of bounded clique-width (2003) Lecture Notes in Comput. Sci., 2880, pp. 370-382. , Graph-Theoretic Concepts in Computer Science Springer Berlin
  • West, D., (2000) Introduction to Graph Theory, , second ed. Prentice Hall

Citas:

---------- APA ----------
Bonomo, F., Grippo, L.N., Milanič, M. & Safe, M.D. (2016) . Graph classes with and without powers of bounded clique-width. Discrete Applied Mathematics, 199, 3-15.
http://dx.doi.org/10.1016/j.dam.2015.06.010
---------- CHICAGO ----------
Bonomo, F., Grippo, L.N., Milanič, M., Safe, M.D. "Graph classes with and without powers of bounded clique-width" . Discrete Applied Mathematics 199 (2016) : 3-15.
http://dx.doi.org/10.1016/j.dam.2015.06.010
---------- MLA ----------
Bonomo, F., Grippo, L.N., Milanič, M., Safe, M.D. "Graph classes with and without powers of bounded clique-width" . Discrete Applied Mathematics, vol. 199, 2016, pp. 3-15.
http://dx.doi.org/10.1016/j.dam.2015.06.010
---------- VANCOUVER ----------
Bonomo, F., Grippo, L.N., Milanič, M., Safe, M.D. Graph classes with and without powers of bounded clique-width. Discrete Appl Math. 2016;199:3-15.
http://dx.doi.org/10.1016/j.dam.2015.06.010