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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom