Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

Given integers m1,.,mℓ, the weighted clique graph of G is the clique graph K(G), in which there is a weight assigned to each complete set S of size mi of K(G), for each i=1,.,ℓ. This weight equals the cardinality of the intersection of the cliques of G corresponding to S. We characterize weighted clique graphs in similar terms as Roberts and Spencer's characterization of clique graphs. Further we characterize several classical graph classes in terms of their weighted clique graphs, providing a common framework for describing some different well-known classes of graphs, as hereditary clique-Helly graphs, split graphs, chordal graphs, interval graphs, proper interval graphs, line graphs, among others. © 2013 Elsevier B.V. All rights reserved.

Registro:

Documento: Artículo
Título:Characterization of classical graph classes by weighted clique graphs
Autor:Bonomo, F.; Szwarcfiter, J.L.
Filiación:DC, FCEN, Universidad de Buenos Aires, Argentina
IMAS-CONICET, Universidad de Buenos Aires, Argentina
COPPE, Universidade Federal Do Rio de Janeiro, Brazil
IM, Universidade Federal Do Rio de Janeiro, Brazil
NCE, Universidade Federal Do Rio de Janeiro, Brazil
Palabras clave:Graph classes structural characterization; Weighted clique graphs; Characterization; Graph theory; Cardinalities; Chordal graphs; Clique graphs; Graph class; Interval graph; Proper interval graphs; Split graphs; Structural characterization; Graphic methods
Año:2014
Volumen:165
Página de inicio:83
Página de fin:95
DOI: http://dx.doi.org/10.1016/j.dam.2013.04.013
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_v165_n_p83_Bonomo

Referencias:

  • Alcón, L., Faria, L., De Figueiredo, C., Gutierrez, M., The complexity of clique graph recognition (2009) Theoretical Computer Science, 410, pp. 2072-2083
  • Barrionuevo, J., Calvo, A., (2004) Sobre Grafos Circulares y Sin Diamantes, , M.Sc. Thesis, Departamento de Computación, FCEyN, Universidad de Buenos Aires, Buenos Aires (in Spanish)
  • Beineke, L.W., Derived graphs of digraphs (1968) Beiträge Zur Graphentheorie, pp. 17-33. , H. Sachs, H.-J. Voss, H.-J. Walter, Teubner Leipzig
  • Beineke, L.W., Characterizations of derived graphs (1970) Journal of Combinatorial Theory, 9, pp. 129-135
  • Berge, C., (1985) Graphs and Hypergraphs, , North-Holland Amsterdam
  • Bonomo, F., Szwarcfiter, J.L., On weighted clique graphs (2010) Matemática Contemporânea, 39, pp. 9-22
  • Brandstädt, A., Chepoi, V., Dragan, F., Voloshin, V., Dually chordal graphs (1998) SIAM Journal on Discrete Mathematics, 11, pp. 437-455
  • Buneman, P., A characterization of rigid circuit graphs (1974) Discrete Mathematics, 9, pp. 205-212
  • Chong-Keang, L., Yee-Hock, P., On graphs without multicliqual edges (1981) Journal of Graph Theory, 5, pp. 443-451
  • Dourado, M.C., Protti, F., Szwarcfiter, J.L., Complexity aspects of the Helly property: Graphs and hypergraphs (2009) The Electronic Journal of Combinatorics, 17, pp. 1-53
  • Escalante, F., Über iterierte clique-graphen (1973) Abhandlungen Aus Dem Mathematischen Seminar der Universität Hamburg, 39, pp. 59-68
  • Escalante, F., Toft, B., On clique-critical graphs (1974) Journal of Combinatorial Theory, Series B, 17, pp. 170-182
  • Evans, T.S., Clique graphs and overlapping communities (2010) Journal of Statistical Mechanics: Theory and Experiment, p. 12037
  • Fulkerson, D., Gross, O., Incidence matrices and interval graphs (1965) Pacific Journal of Mathematics, 15 (3), pp. 835-855
  • Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs (1974) Journal of Combinatorial Theory, Series B, 16, pp. 47-56
  • Gavril, F., Generating the maximum spanning trees of a weighted graph (1987) Journal of Algorithms, 8, pp. 592-597
  • Golumbic, M., Trivially perfect graphs (1978) Discrete Mathematics, 24, pp. 105-107
  • Gutierrez, M., Tree-clique graphs (1996) Proceedings of the Workshop Internacional de Combinatória, pp. 7-26. , Rio de Janeiro, Brazil
  • Gutierrez, M., Szwarcfiter, J., Tondato, S., Clique trees of chordal graphs: Leafage and 3-asteroidals (2008) Electronic Notes in Discrete Mathematics, 30, pp. 237-242
  • Habib, M., Stacho, J., A decomposition theorem for chordal graphs and its applications (2009) Electronic Notes in Discrete Mathematics, 34, pp. 561-565
  • Habib, M., Stacho, J., Reduced clique graphs of chordal graphs (2012) European Journal of Combinatorics, 33, pp. 712-735
  • Hamelink, R., A partial characterization of clique graphs (1968) Journal of Combinatorial Theory, Series B, 5, pp. 192-197
  • Hedetniemi, S., Slater, P., Line graphs of triangleless graphs and iterated clique graphs (1972) Lecture Notes in Mathematics, 303, pp. 139-147
  • Hedman, B., Clique graphs of time graphs (1984) Journal of Combinatorial Theory, Series B, 37 (3), pp. 270-278
  • Kloks, T., Kratsch, D., Müller, H., Dominoes (1995) Lecture Notes in Computer Science, 903, pp. 106-120
  • Krausz, J., Démonstration nouvelle d'un théorème de Whitney sur les réseaux (1943) Matematikai És Fizikai Lapok, 50, pp. 75-85
  • Lin, I.J., McKee, T.A., West, D.B., The leafage of a chordal graph (1998) Discussiones Mathematicae Graph Theory, 18, pp. 23-48
  • Lucchesi, C., Picinin De Mello, C., Szwarcfiter, J., On clique-complete graphs (1998) Discrete Mathematics, 183, pp. 247-254
  • McKee, T.A., Clique multigraphs (1991) Graph Theory, Combinatorics, Algorithms and Applications, pp. 371-379. , Y. Alavi, F.R.K. Chung, R.L. Graham, D.S. Hsu, SIAM Philadelphia
  • McKee, T.A., Clique pseudographs and pseudo duals (1994) Ars Combinatoria, 38, pp. 161-173
  • McKee, T.A., Restricted circular-arc graphs and clique cycles (2003) Discrete Mathematics, 263, pp. 221-231
  • McKee, T.A., Clique graph characterizations of strongly chordal graphs (2013) The Journal of Combinatorial Mathematics and Combinatorial Computing, , (in press)
  • McKee, T.A., McMorris, F.R., (1999) Topics in Intersection Graph Theory, , SIAM Philadelphia
  • Metelsky, Y., Tyshkevich, R., Line graphs of Helly hypergraphs (2003) SIAM Journal on Discrete Mathematics, 16 (3), pp. 438-448
  • Prisner, E., Hereditary clique-Helly graphs (1993) The Journal of Combinatorial Mathematics and Combinatorial Computing, 14, pp. 216-220
  • Roberts, F.S., Indifference graphs (1969) Proof Techniques in Graph Theory, pp. 139-146. , F. Harary, Academic Press
  • Roberts, F., Spencer, J., A characterization of clique graphs (1971) Journal of Combinatorial Theory, Series B, 10, pp. 102-108
  • Shibata, Y., On the tree representation of chordal graphs (1988) Journal of Graph Theory, 12 (23), pp. 421-428
  • Šoltés, L., Forbidden induced subgraphs for line graphs (1994) Discrete Mathematics, 132, pp. 391-394
  • Syslo, M.M., A labeling algorithm to recognize a line graph and output its root graph (1982) Information Processing Letters, 15, pp. 28-30
  • Szwarcfiter, J., Bornstein, C., Clique graphs of chordal and path graphs (1994) SIAM Journal on Discrete Mathematics, 7, pp. 331-336
  • Tsukiyama, S., Idle, M., Ariyoshi, H., Shirakawa, Y., A new algorithm for generating all the maximal independent sets (1977) SIAM Journal on Computing, 6 (3), pp. 505-517
  • Van Rooij, A., Wilf, H., The interchange graphs of a finite graph (1965) Acta Mathematica Academiae Scientiarum Hungaricae, 16, pp. 263-269
  • Wallis, W.D., Zhang, G.-H., On maximal clique irreducible graphs (1990) The Journal of Combinatorial Mathematics and Combinatorial Computing, 8, pp. 187-193
  • Walter, J.R., Representations of chordal graphs as subtrees of a tree (1978) Journal of Graph Theory, 2 (3), pp. 265-267

Citas:

---------- APA ----------
Bonomo, F. & Szwarcfiter, J.L. (2014) . Characterization of classical graph classes by weighted clique graphs. Discrete Applied Mathematics, 165, 83-95.
http://dx.doi.org/10.1016/j.dam.2013.04.013
---------- CHICAGO ----------
Bonomo, F., Szwarcfiter, J.L. "Characterization of classical graph classes by weighted clique graphs" . Discrete Applied Mathematics 165 (2014) : 83-95.
http://dx.doi.org/10.1016/j.dam.2013.04.013
---------- MLA ----------
Bonomo, F., Szwarcfiter, J.L. "Characterization of classical graph classes by weighted clique graphs" . Discrete Applied Mathematics, vol. 165, 2014, pp. 83-95.
http://dx.doi.org/10.1016/j.dam.2013.04.013
---------- VANCOUVER ----------
Bonomo, F., Szwarcfiter, J.L. Characterization of classical graph classes by weighted clique graphs. Discrete Appl Math. 2014;165:83-95.
http://dx.doi.org/10.1016/j.dam.2013.04.013