Strongly distance-balanced graphs and graph productsBalakrishnan, Kannan (Avtor) Changat, Manoj (Avtor) Peterin, Iztok (Avtor) Špacapan, Simon (Avtor) Šparl, Primož (Avtor) Subhamathi, Ajitha R. (Avtor) matematikateorija grafovrazdaljno uravnoteženi grafimathematicsgraph theorydistance-balanced graphaA 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.20082015-07-10 15:07:26Delo ni kategorizirano51773UDK: 519.17OceCobissID: 25427968COBISS_ID: 15079769DOI: 10.1016/j.ejc.2008.09.018ISSN pri članku: 0195-6698NUK URN: URN:SI:UM:DK:E4TPOWHCsl