Strongly distance-balanced graphs and graph products

Kannan Balakrishnan (Avtor), Manoj Changat (Avtor), Iztok Peterin (Avtor), Simon Špacapan (Avtor), Primož Šparl (Avtor), Ajitha R. Subhamathi (Avtor)

Povzetek

A graph ▫$G$▫ is strongly distance-balanced if for every edge ▫$uv$▫ of ▫$G$▫ and every ▫$i \ge 0$▫ the number of vertices ▫$x$▫ with ▫$d(x,u) = d(x,v)-1 = i$▫ equals the number of vertices ▫$y$▫ with ▫$d(y,v) = d(y,u)-1 = 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 distance-balanced 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, where m is the number of edges and ▫$n$▫ the number of vertices of the graph in question, are given.

Ključne besede

matematika;teorija grafov;razdaljno uravnoteženi grafi;mathematics;graph theory;distance-balanced grapha;

Podatki

Jezik:	Angleški jezik
Leto izida:	2008
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
UDK:	519.17
COBISS:	15079769
ISSN:	0195-6698
Št. ogledov:	1090
Št. prenosov:	81
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Neznan jezik
Sekundarni naslov:	Krepko razdaljno uravnoteženi grafi in produkti grafov
Sekundarne ključne besede:	matematika;teorija grafov;razdaljno uravnoteženi grafi;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 1048-1053
Letnik:	ǂVol. ǂ30
Zvezek:	ǂiss. ǂ5
Čas izdaje:	2009
DOI:	10.1016/j.ejc.2008.09.018
ID:	1474166