# l-distance-balanced graphs
ID Miklavič, Štefko (Author), ID Šparl, Primož (Author) URL - Presentation file, Visit https://doi.org/10.1016/j.dam.2018.03.011 Abstract
Graf ▫$\Gamma$▫ je razdaljno uravnotežen, če v njem za poljuben par sosednjih vozlišč ▫$u$▫ in ▫$v$▫ velja, da je število vozlišč grafa ▫$\Gamma$▫, ki so bližje ▫$u$▫ kot ▫$v$▫, enako številu vozlišč grafa ▫$\Gamma$▫, ki so bližje ▫$v$▫ kot ▫$u$▫. Ti grafi so sicer zanimivi že sami po sebi, v okviru teorije grafov, pomembni pa so tudi zaradi možnosti uporabe na drugih področjih, kot sta na primer matematična kemija in teorija komunikacijskih omrežij. V članku se posvetimo naravni posplošitvi koncepta razdaljne uravnoteženosti, ki jo le leta 2014 vpeljal Boštjan Frelih. Pravimo, da je graf ▫$\Gamma$▫ ▫$\ell$▫-razdaljno uravnotežen, če za poljuben par vozlišč ▫$u$▫ in ▫$v$▫ na razdalji ▫$\ell$▫ v grafu ▫$\Gamma$▫ velja, da je število vozlišč grafa ▫$\Gamma$▫, ki so bližje ▫$u$▫ kot ▫$v$▫, enako številu vozlišč grafa ▫$\Gamma$▫, ki so bližje ▫$v$▫ kot ▫$u$▫. V članku pokažemo nekaj splošnih lastnosti takšnih grafov in konstruiramo vrsto različnih primerov. Posebej se posvetimo grafom premera največ 3 in študiramo lastnost ▫$\ell$▫-razdaljne uravnoteženosti v kubičnih grafih. Med drugim se posvetimo tej lastnosti v dobro znanih posplošenih Petersenovih grafih.

Language: English distance-balanced, l-distance-balanced, highly distance-balanced Article 1.01 - Original Scientific Article PEF - Faculty of Education 2018 Str. 143-154 Vol. 244 20.500.12556/RUL-125780 519.17 0166-218X 10.1016/j.dam.2018.03.011 1540239812 07.04.2021 292 77    Copy citation AddThis uses cookies that require your consent. Edit consent...

## Record is a part of a journal

Title: Discrete applied mathematics Discrete appl. math. Elsevier 0166-218X 25342464 ## Secondary language

Language: English l-razdaljno uravnoteženi grafi A graph ▫$\varGamma$▫ is distance-balanced if for each pair ▫$u$▫, ▫$v$▫ of adjacent vertices of ▫$\varGamma$▫ the number of vertices closer to ▫$u$▫ than to ▫$v$▫ is equal to the number of vertices closer to ▫$v$▫ than to ▫$u$▫. Apart from the interest in these graphs from the graph theoretical point of view they have applications in other areas of research, for instance in mathematical chemistry and communication networks, and have thus been studied from various different points of view in the literature. In this paper we study a very natural generalization of the concept of distance-balancedness, introduced by B. Frelih. Let ▫$\ell$▫ denote a positive integer. A connected graph ▫$\varGamma$▫ of diameter at least ▫$\ell$▫ is said to be ▫$\ell$▫ distance-balanced whenever for any pair of vertices ▫$u$▫, ▫$v$▫ of ▫$\varGamma$▫ at distance ▫$\ell$▫, the number of vertices closer to ▫$u$▫ than to ▫$v$▫ is equal to the number of vertices closer to ▫$v$▫ than to ▫$u$▫. We obtain some general results on ▫$\ell$▫-distance-balanced graphs and provide various examples. We study those of diameter at most 3 in more detail and investigate the ▫$\ell$▫-distance-balancedness property of cubic graphs. In particular, we analyze this property for the generalized Petersen graphs.

Back