Premium
Simultaneous embeddings of graphs as median and antimedian subgraphs
Author(s) -
Balakrishnan K.,
Brešar B.,
Kovše M.,
Changat M.,
Subhamathi A.R.,
Klavžar S.
Publication year - 2010
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20350
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , undirected graph , regular polygon , bound graph , connectivity , integer (computer science) , discrete mathematics , graph power , line graph , computer science , geometry , programming language
The distance D G ( v ) of a vertex v in an undirected graph G is the sum of the distances between v and all other vertices of G . The set of vertices in G with maximum (minimum) distance is the antimedian (median) set of a graph G . It is proved that for arbitrary graphs G and J and a positive integer r > 2, there exists a connected graph H , such that G is the antimedian and J the median subgraphs of H , respectively, and that d H ( G , J ) = r . When both G and J are connected, G and J can in addition be made convex subgraphs of H . © 2009 Wiley Periodicals, Inc. NETWORKS, 2010