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:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UL FMF - Fakulteta za matematiko in fiziko
UDK: 519.17
COBISS: 15079769 Povezava se bo odprla v novem oknu
ISSN: 0195-6698
Št. ogledov: 1090
Št. prenosov: 81
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

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
Priporočena dela:
, ni podatka o podnaslovu
, ni podatka o podnaslovu
, ni podatka o podnaslovu
, ni podatka o podnaslovu
, diplomsko delo