# 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

## Access Full Article

top## Abstract

top## How to cite

topBoš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] 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] 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] 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] 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] 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. Zbl1055.05040
- [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] 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] 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] 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] 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] 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] 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] 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. Zbl0916.68106
- [16] S. Klavžar and M. Kovse, Partial cubes and their τ-graphs, European J. Combin. 28 (2007) 1037-1042. Zbl1120.05027
- [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] 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] 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. Zbl0064.17805
- [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] A. Vesel, Characterization of resonance graphs of catacondensed hexagonal graphs, MATCH Commun. Math. Comput. Chem. 53 (2005) 195-208. Zbl1077.05088
- [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 ?

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