The periphery graph of a median graph

Boštjan Brešar; Manoj Changat; Ajitha R. Subhamathi; Aleksandra Tepeh

Discussiones Mathematicae Graph Theory (2010)

  • Volume: 30, Issue: 1, page 17-32
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Boštjan Brešar, et al. "The periphery graph of a median graph." Discussiones Mathematicae Graph Theory 30.1 (2010): 17-32. <http://eudml.org/doc/270988>.

@article{BoštjanBrešar2010,
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.},
author = {Boštjan Brešar, Manoj Changat, Ajitha R. Subhamathi, Aleksandra Tepeh},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {median graph; Cartesian product; geodesic; periphery; peripheral expansion},
language = {eng},
number = {1},
pages = {17-32},
title = {The periphery graph of a median graph},
url = {http://eudml.org/doc/270988},
volume = {30},
year = {2010},
}

TY - JOUR
AU - Boštjan Brešar
AU - Manoj Changat
AU - Ajitha R. Subhamathi
AU - Aleksandra Tepeh
TI - The periphery graph of a median graph
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 1
SP - 17
EP - 32
AB - 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.
LA - eng
KW - median graph; Cartesian product; geodesic; periphery; peripheral expansion
UR - http://eudml.org/doc/270988
ER -

References

top
  1. [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. Zbl1227.05137
  2. [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. Zbl0848.05053
  3. [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. Zbl0810.05057
  4. [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. Zbl0682.05031
  5. [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. [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. Zbl1055.05040
  7. [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. Zbl1141.05071
  8. [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. Zbl1194.05128
  9. [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. Zbl1133.05024
  10. [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. Zbl1154.05025
  11. [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. Zbl0961.05019
  12. [12] D. Djoković, Distance preserving subgraphs of hypercubes, J. Combin. Theory (B) 14 (1973) 263-267, doi: 10.1016/0095-8956(73)90010-5. Zbl0245.05113
  13. [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. Zbl0927.05078
  14. [14] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (Wiley-Interscience, New York, 2000). 
  15. [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. Zbl0916.68106
  16. [16] S. Klavžar and M. Kovse, Partial cubes and their τ-graphs, European J. Combin. 28 (2007) 1037-1042. Zbl1120.05027
  17. [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. Zbl0931.05072
  18. [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. Zbl1003.05089
  19. [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. [20] J. Mycielski, Sur le coloriage des graphs, Colloq. Math. 3 (1955) 161-162. Zbl0064.17805
  21. [21] I. Peterin, A characterization of planar median graphs, Discuss. Math. Graph Theory 26 (2006) 41-48, doi: 10.7151/dmgt.1299. Zbl1105.05017
  22. [22] A. Vesel, Characterization of resonance graphs of catacondensed hexagonal graphs, MATCH Commun. Math. Comput. Chem. 53 (2005) 195-208. Zbl1077.05088
  23. [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. Zbl0529.05055

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.