Download PDF - The periphery graph of a median graphAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

The periphery graph of a median graph

Authors 1, 2, 2, 3

Affiliations

  1. Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia
  2. Department of Futures Studies, University of Kerala, Trivandrum-695034, India
  3. Faculty of Electrical Engineering and Computer Science, University of Maribor, Slovenia

Abstract

The periphery graph of a median graph is the intersection graph of its peripheral subgraphs. We show that every graph without a universal vertex can be realized as the periphery graph of a median graph. We characterize those median graphs whose periphery graph is the join of two graphs and show that they are precisely Cartesian products of median graphs. Path-like median graphs are introduced as the graphs whose periphery graph has independence number 2, and it is proved that there are path-like median graphs with arbitrarily large geodetic number. Peripheral expansion with respect to periphery graph is also considered, and connections with the concept of crossing graph are established.

Keywords

ENG
median graph, Cartesian product, geodesic, periphery, peripheral expansion

Bibliography

  1. K. Balakrishnan, B. Brešar, M. Changat, W. Imrich, S. Klavžar, M. Kovse and A.R. Subhamathi, On the remoteness function in median graphs, Discrete Appl. Math. 157 (2009) 3679-3688, doi: 10.1016/j.dam.2009.07.007.
  2. H.-J. Bandelt and V. Chepoi, Graphs of acyclic cubical complexes, European J. Combin. 17 (1996) 113-120, doi: 10.1006/eujc.1996.0010.
  3. H.-J. Bandelt, H.M. Mulder and E. Wilkeit, Quasi-median graphs and algebras, J. Graph Theory 18 (1994) 681-703, doi: 10.1002/jgt.3190180705.
  4. H.-J. Bandelt and M. van de Vel, Embedding topological median algebras in products of dendrons, Proc. London Math. Soc. 58 (1989) 439-453, doi: 10.1112/plms/s3-58.3.439.
  5. H.-J. Bandelt, L. Quintana-Murci, A. Salas and V. Macaulay, The fingerprint of phantom mutations in mitochondrial DNA data, American J. Human Genetics 71 (2002) 1150-1160, doi: 10.1086/344397.
  6. B. Brešar, Arboreal structure and regular graphs of median-like classes, Discuss. Math. Graph Theory 23 (2003) 215-225, doi: 10.7151/dmgt.1198.
  7. B. Brešar and S. Klavžar, Crossing graphs as joins of graphs and Cartesian products of median graphs, SIAM J. Discrete Math. 21 (2007) 26-32, doi: 10.1137/050622997.
  8. B. Brešar and T. Kraner Sumenjak, Cube intersection concepts in median graphs, Discrete Math. 309 (2009) 2990-2997, doi: 10.1016/j.disc.2008.07.032.
  9. B. Brešar and A. Tepeh Horvat, Crossing graphs of fiber-complemented graphs, Discrete Math. 308 (2008) 1176-1184, doi: 10.1016/j.disc.2007.04.005.
  10. B. Brešar and A. Tepeh Horvat, On the geodetic number of median graphs, Discrete Math. 308 (2008) 4044-4051, doi: 10.1016/j.disc.2007.07.119.
  11. M. Chastand, Fiber-complemented graphs, I. Structure and invariant subgraphs, Discrete Math. 226 (2001) 107-141, doi: 10.1016/S0012-365X(00)00183-7.
  12. D. Djoković, Distance preserving subgraphs of hypercubes, J. Combin. Theory (B) 14 (1973) 263-267, doi: 10.1016/0095-8956(73)90010-5.
  13. A. Dress, K. Huber and V. Moulton, Some variations on a theme by Buneman, Ann. Combin. 1 (1997) 339-352, doi: 10.1007/BF02558485.
  14. W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (Wiley-Interscience, New York, 2000).
  15. W. Imrich, S. Klavžar and H.M. Mulder, Median graphs and triangle-free graphs, SIAM J. Discrete Math. 12 (1999) 111-118, doi: 10.1137/S0895480197323494.
  16. S. Klavžar and M. Kovse, Partial cubes and their τ-graphs, European J. Combin. 28 (2007) 1037-1042.
  17. S. Klavžar and H.M. Mulder, Median graphs: characterizations, location theory and related structures, J. Combin. Math. Combin. Comp. 30 (1999) 103-127.
  18. S. Klavžar and H.M. Mulder, Partial cubes and crossing graphs, SIAM J. Discrete Math. 15 (2002) 235-251, doi: 10.1137/S0895480101383202.
  19. H.M. Mulder, The expansion procedure for graphs, in: R. Bodendiek ed., Contemporary Methods in Graph Theory (B.I.-Wissenschaftsverlag, Manhaim/Wien/Zürich, 1990) 459-477.
  20. J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955) 161-162.
  21. I. Peterin, A characterization of planar median graphs, Discuss. Math. Graph Theory 26 (2006) 41-48, doi: 10.7151/dmgt.1299.
  22. A. Vesel, Characterization of resonance graphs of catacondensed hexagonal graphs, MATCH Commun. Math. Comput. Chem. 53 (2005) 195-208.
  23. P. Winkler, Isometric embeddings in products of complete graphs, Discrete Appl. Math. 7 (1984) 221-225, doi: 10.1016/0166-218X(84)90069-6.
Discussiones Mathematicae Graph Theory
2010/30/1
Export to PBN, Opens in new tab
Pages:
17-32
Main language of publication
English
Received
2008-06-11
Accepted
2009-01-05
Published
2010

DOI: 10.7151/dmgt.1473

Exact and natural sciences