×

Cube intersection concepts in median graphs. (English) Zbl 1194.05128

Summary: We study different classes of intersection graphs of maximal hypercubes of median graphs. For a median graph \(G\) and \(k\geq 0\), the intersection graph \(\mathcal Q_k(G)\) is defined as the graph whose vertices are maximal hypercubes (by inclusion) in \(G\), and two vertices \(H_x\) and \(H_y\) in \(\mathcal Q_k(G)\) are adjacent whenever the intersection \(H_x\cap H_y\) contains a subgraph isomorphic to \(Q_k\). Characterizations of clique-graphs in terms of these intersection concepts when \(k>0\), are presented. Furthermore, we introduce the so-called maximal 2-intersection graph of maximal hypercubes of a median graph \(G\), denoted \(\mathcal Q_{\text m2}(G)\), whose vertices are maximal hypercubes of \(G\), and two vertices are adjacent if the intersection of the corresponding hypercubes is not a proper subcube of some intersection of two maximal hypercubes. We show that a graph \(H\) is diamond-free if and only if there exists a median graph \(G\) such that \(H\) is isomorphic to \(\mathcal Q_{\text m2}(G)\). We also study convergence of median graphs to the one-vertex graph with respect to all these operations.

MSC:

05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] H.-J. Bandelt, Characterizing median graphs, manuscript, 1982; H.-J. Bandelt, Characterizing median graphs, manuscript, 1982
[2] Bandelt, H.-J.; Chepoi, V., Graphs of acyclic cubical complexes, European J. Combin., 17, 113-120 (1996) · Zbl 0848.05053
[3] H.-J. Bandelt, V. Chepoi, Metric graph theory and geometry — a survey, Contemp Math. (in press); H.-J. Bandelt, V. Chepoi, Metric graph theory and geometry — a survey, Contemp Math. (in press) · Zbl 1169.05015
[4] Bandelt, H.-J.; Prisner, E., Clique graphs and Helly graphs, J. Combin. Theory Ser. B, 51, 34-45 (1991) · Zbl 0726.05060
[5] Bandelt, H.-J.; van de Vel, M., Embedding topological median algebras in products of dendrons, Proc. London Math. Soc. (3), 58, 439-453 (1989) · Zbl 0682.05031
[6] Bandelt, H.-J.; van de Vel, M., Superextensions and the depth of median graphs, J. Combin. Theory Ser. A, 57, 187-202 (1991) · Zbl 0756.05091
[7] Berge, C., Hypergraphs (1989), North-Holland: North-Holland Amsterdam · Zbl 0334.05117
[8] Bornstein, C. F.; Szwarcfiter, J. L., Clique graphs of chordal graphs and path graphs, SIAM J. Discrete Math., 7, 331-336 (1994) · Zbl 0798.05046
[9] Bornstein, C. F.; Szwarcfiter, J. L., On clique convergent graphs, Graphs Combin., 11, 213-220 (1995) · Zbl 0841.05094
[10] Bornstein, C. F.; Szwarcfiter, J. L., Iterated clique graphs with increasing diameters, J. Graph Theory, 28, 147-154 (1998) · Zbl 0920.05024
[11] Brandstädt, A.; Dragan, F.; Chepoi, V.; Voloshin, V., Dually chordal graphs, SIAM J. Discrete Math., 11, 437-455 (1998) · Zbl 0909.05037
[12] Brandstädt, A.; Le, V. B.; Spinrad, J. P., Graphs Classes: A Survey (1999), SIAM: SIAM Philadelphia
[13] Brešar, B., Intersection graphs of maximal hypercubes, European J. Combin., 24, 195-209 (2003) · Zbl 1018.05091
[14] Brešar, B.; Imrich, W.; Klavžar, S., Tree-like isometric subgraphs of hypercubes, Discuss. Math. Graph Theory, 23, 227-240 (2003) · Zbl 1055.05129
[15] Brešar, B.; Klavžar, S.; Škrekovski, R., Quasi-median graphs, their generalizations, and tree-like equalities, European J. Combin., 24, 557-572 (2003) · Zbl 1022.05070
[16] Chang-Keang, L.; Yee-Hock, P., On graphs without multicliqual edges, J. Graph Theory, 5, 443-451 (1981) · Zbl 0492.05056
[17] V. Chepoi, personal communication; V. Chepoi, personal communication
[18] Chepoi, V., Graphs of some CAT(0) complexes, Adv. Appl. Math., 24, 125-179 (2000) · Zbl 1019.57001
[19] Chung, F. R.K.; Graham, R. L.; Saks, M. E., Dynamic search in graphs, (Johnson, D. S.; Nishizeki, T.; Takao, N.; Wilf, H. S., Discrete Algorithms and Complexity (1987), Academic Press: Academic Press San Diego), 351-388 · Zbl 0643.68083
[20] Gutierrez, M., Intersection graphs and the clique operator, Graphs Combin., 17, 237-244 (2001) · Zbl 0978.05066
[21] Hedetniemi, S. T.; Slater, P. J., (Line Graphs of Triangleless Graphs and Iterated Clique Graphs. Line Graphs of Triangleless Graphs and Iterated Clique Graphs, Lecture Notes in Mathematics, vol. 303 (1972), Springer: Springer Berlin), 139-147 · Zbl 0255.05121
[22] Hedman, B., Clique graphs of time graphs, J. Combin. Theory, 3, 270-278 (1984) · Zbl 0547.05056
[23] Imrich, W.; Klavžar, S., Product Graphs: Structure and Recognition (2000), John Wiley & Sons: John Wiley & Sons New York
[24] Imrich, W.; Klavžar, S.; Mulder, H. M., Median graphs and triangle-free graphs, SIAM J. Discrete Math., 12, 111-118 (1999) · Zbl 0916.68106
[25] Isbell, J. R., Median algebra, Trans. Amer. Math Soc., 260, 319-362 (1980) · Zbl 0446.06007
[26] Klavžar, S.; Mulder, H. M., Median graphs: Characterizations, location theory and related structures, J. Combin. Math. Combin. Comput., 30, 103-127 (1999) · Zbl 0931.05072
[27] Klavžar, S.; Mulder, H. M.; Škrekovski, R., An Euler-type formula for median graphs, Discrete Math., 187, 255-258 (1998) · Zbl 0957.05031
[28] Larrion, F.; Neumann-Lara, V., A family of clique divergent graphs with linear growth, Graphs Combin., 13, 263-266 (1997) · Zbl 0892.05041
[29] Mahadev, N. V.R.; Wang, T. M., On uniquely intersectable graphs, Discrete Math., 207, 149-159 (1999) · Zbl 0944.05085
[30] McKee, T. A.; McMorris, F. R., Topics in Intersection Graph Theory (1999), SIAM: SIAM Philadelphia · Zbl 0945.05003
[31] Mulder, H. M., The structure of median graphs, Discrete Math., 24, 197-204 (1978) · Zbl 0394.05038
[32] Mulder, H. M., The Interval Function of a Graph, Mathematical Centre Tracts, vol. 132 (1980), Matematisch Centrum: Matematisch Centrum Amsterdam · Zbl 0446.05039
[33] Mulder, H. M., The expansion procedure for graphs, (Bodendiek, R., Contemporary Methods in Graph Theory (1990), B.I.-Wissenschaftsverlag: B.I.-Wissenschaftsverlag Manhaim, Wien, Zürich), 459-477 · Zbl 0744.05064
[34] Peyrat, C.; Rall, D. F.; Slater, P. J., On iterated clique graphs with increasing diameters, J. Graph Theory, 10, 167-171 (1986) · Zbl 0596.05036
[35] Pizaña, M. A., Distances and diameters on iterated clique graphs, Disrete Appl. Math., 141, 255-261 (2004) · Zbl 1043.05042
[36] Prisner, E., Graph Dynamics (1995), Longman: Longman Harlow · Zbl 0848.05001
[37] Roberts, F. S.; Spencer, J. H., A characterization of clique graphs, J. Combin. Theory, 10, 102-108 (1971) · Zbl 0215.05801
[38] Szwarcfiter, J. L., A survey on clique graphs, (Reed, B. A.; Linhares-Sales, C., Recent Advances in Algorithms and Combinatorics (2003), Springer: Springer New York), 109-136 · Zbl 1027.05071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.