|
Title:
|
Strongly distance-balanced graphs and graph products |
|
Author:
|
Kannan, Balakrishnan; Manoj, Changat; Iztok, Peterin; Simon, Spacapan; Primoz, Sparl; Ajitha, Subhamathi R
|
|
Abstract:
|
A graph G is strongly distance-balanced if for every edge uv of
G and every i 0 the number of vertices x with d.x; u/ D d.x; v/ 1 D i equals the number of vertices y with d.y; v/ D d.y; u/ 1 D i. It is proved that the strong product of graphs is
strongly distance-balanced if and only if both factors are strongly
distance-balanced. It is also proved that connected components of
the direct product of two bipartite graphs are strongly distancebalanced
if and only if both factors are strongly distance-balanced.
Additionally, a new characterization of distance-balanced graphs
and an algorithm of time complexity O.mn/ for their recognition,
wheremis the number of edges and n the number of vertices of the
graph in question, are given |
|
Description:
|
European Journal of Combinatorics 30 (2009) 1048- 1053 |
|
URI:
|
http://dyuthi.cusat.ac.in/purl/4198
|
|
Date:
|
2008-10-31 |