l-distance-balanced graphs

Miklavič, Štefko (author), Šparl, Primož (author)

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
• Keywords: distance-balanced, l-distance-balanced, highly distance-balanced
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: PEF - Faculty of Education
• Year: 2018
• Number of pages: Str. 143-154
• Numbering: Vol. 244
• PID: 20.500.12556/RUL-125780
• UDC: 519.17
• ISSN on article: 0166-218X
• DOI: 10.1016/j.dam.2018.03.011
• COBISS.SI-ID: 1540239812
• Publication date in RUL: 07.04.2021

Record is a part of a journal

• Title: Discrete applied mathematics
• Shortened title: Discrete appl. math.
• Publisher: Elsevier
• ISSN: 0166-218X
• COBISS.SI-ID: 25342464

Secondary language

• Language: English
• Title: l-razdaljno uravnoteženi grafi

Abstract

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.