PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2010 | 30 | 1 | 17-32
Tytuł artykułu

The periphery graph of a median graph

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
30
Numer
1
Strony
17-32
Opis fizyczny
Daty
wydano
2010
otrzymano
2008-06-11
poprawiono
2009-01-05
zaakceptowano
2009-01-05
Twórcy
  • Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia
  • Department of Futures Studies, University of Kerala, Trivandrum-695034, India
  • Department of Futures Studies, University of Kerala, Trivandrum-695034, India
  • Faculty of Electrical Engineering and Computer Science, University of Maribor, Slovenia
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1473
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.