Distance-balanced graphs: Symmetry conditions

Kutnar, Klavdija; Malnič, Aleksander; Marušič, Dragan; Miklavič, Štefko

ENG

Prijava

Prva stran / Izpis gradiva

Izpis gradiva

A- | A+ | Natisni

Naslov:	Distance-balanced graphs: Symmetry conditions
Avtorji:	ID Kutnar, Klavdija (Avtor) ID Malnič, Aleksander (Avtor) ID Marušič, Dragan (Avtor) ID Miklavič, Štefko (Avtor)
Datoteke:	http://dx.doi.org/10.1016/j.disc.2006.03.066
Jezik:	Angleški jezik
Vrsta gradiva:	Delo ni kategorizirano
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	IAM - Inštitut Andrej Marušič
Opis:	A graph $X$ is said to be distance-balanced if for any edge $uv$ of $X$ , the number of vertices closer to $u$ than to $v$ is equal to the number of vertices closer to $v$ than to $u$ . A graph $X$ is said to be strongly distance-balanced if for any edge $uv$ of $X$ and any integer $k$ , the number of vertices at distance $k$ from $u$ and at distance $k+1$ from $v$ is equal to the number of vertices at distance $k+1$ from $u$ and at distance $k$ from $v$ . Exploring the connection between symmetry properties of graphs and the metric property of being (strongly) distance-balanced is the main theme of this article. That a vertex-transitive graph is necessarily strongly distance-balanced and thus also distance-balanced is an easy observation. With only a slight relaxation of the transitivity condition, the situation changes drastically: there are infinite families of semisymmetric graphs (that is, graphs which are edge-transitive, but not vertex-transitive) which are distance-balanced, but there are also infinite families of semisymmetric graphs which are not distance-balanced. Results on the distance-balanced property in product graphs prove helpful in obtaining these constructions. Finally, a complete classification of strongly distance-balanced graphs is given for the following infinite families of generalized Petersen graphs: GP $(n,2)$ , GP $(5k+1,k)$ , GP $(3k 3,k)$ , and GP $(2k+2,k)$ .
Ključne besede:	graph theory, graph, distance-balanced graphs, vertex-transitive, semysimmetric, generalized Petersen graph
Leto izida:	2006
Št. strani:	str. 1881-1894
Številčenje:	Vol. 306, iss. 16
PID:	20.500.12556/RUP-835
ISSN:	0012-365X
UDK:	519.17
COBISS.SI-ID:	1714391
Datum objave v RUP:	15.10.2013
Število ogledov:	6955
Število prenosov:	93
Metapodatki:
:	KUTNAR, Klavdija, MALNIČ, Aleksander, MARUŠIČ, Dragan in MIKLAVIČ, Štefko, 2006, Distance-balanced graphs: Symmetry conditions. [na spletu]. 2006. Vol. 306, no. 16, p. 1881–1894. [Dostopano 19 marec 2025]. Pridobljeno s: http://dx.doi.org/10.1016/j.disc.2006.03.066 Kopiraj citat

Skupna ocena:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

Iščem podobna dela... Prosim, počakajte...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Sekundarni jezik

Jezik:	Angleški jezik
Ključne besede:	teorija grafov, razdaljno uravnoteženi grafi, polsimetrični grafi, posplošeni Petersenov graf, tranzitivni grafi

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj