20.500.12556/RUL-125780
l-distance-balanced graphs
l-razdaljno uravnoteženi grafi
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.
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.
distance-balanced
l-distance-balanced
highly distance-balanced
true
false
true
Angleški jezik
Angleški jezik
Članek v reviji
2021-04-07 05:06:08
2021-04-07 09:59:30
2022-09-05 03:52:29
0000-00-00 00:00:00
2018
0
0
Str. 143-154
Vol. 244
July 2018
0000-00-00
NiDoloceno
NiDoloceno
NiDoloceno
0000-00-00
0000-00-00
0000-00-00
519.17
0166-218X
10.1016/j.dam.2018.03.011
1540239812
25342464
https://doi.org/10.1016/j.dam.2018.03.011
1
https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=141642
Pedagoška fakulteta
0
0
0