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

Abstract

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.

Keywords

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

Data

Language: English
Year of publishing:
Typology: 1.01 - Original Scientific Article
Organization: UL FMF - Faculty of Mathematics and Physics
UDC: 519.17
COBISS: 15079769 Link will open in a new window
ISSN: 0195-6698
Views: 1090
Downloads: 81
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: Unknown
Secondary title: Krepko razdaljno uravnoteženi grafi in produkti grafov
Secondary keywords: matematika;teorija grafov;razdaljno uravnoteženi grafi;
URN: URN:SI:UM:
Type (COBISS): Not categorized
Pages: str. 1048-1053
Volume: ǂVol. ǂ30
Issue: ǂiss. ǂ5
Chronology: 2009
DOI: 10.1016/j.ejc.2008.09.018
ID: 1474166
Recommended works:
, no subtitle data available
, no subtitle data available
, no subtitle data available
, no subtitle data available
, diplomsko delo