20.500.12556/DKUM-51773 Strongly distance-balanced graphs and graph products Krepko razdaljno uravnoteženi grafi in produkti grafov 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. matematika teorija grafov razdaljno uravnoteženi grafi mathematics graph theory distance-balanced grapha true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 15:07:26 2015-07-10 15:07:26 2022-05-30 03:07:19 2019-07-11 07:27:55 2008 0 0 str. 1048-1053 iss. 5 Vol. 30 2009 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 25427968 15079769 10.1016/j.ejc.2008.09.018 0195-6698 URN:SI:UM:DK:E4TPOWHC http://dx.doi.org/10.1016/j.ejc.2008.09.018 1 https://dk.um.si/Dokument.php?lang=slv&id=76333 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0