Distance-balanced graphs

Janja Jerebic (Avtor), Sandi Klavžar (Avtor), Douglas F. Rall (Avtor)

Povzetek

V članku so vpeljani razdaljno uravnoteženi grafi kot grafi, v katerih ima vsaka povezava ▫$uv$▫ naslednjo lastnost: število točk, ki so bližje ▫$u$▫ kot ▫$v$▫, je enako kot število točk, ki so bližje ▫$v$▫ kot ▫$u$▫. Dobljene so osnovne lastnosti teh grafov. Novi koncept je povezan z grafovskimi simetrijami, študirane so tudi lokalne operacije na grafih glede na razdaljno uravnoteženost. Karakterizirani so razdaljno uravnoteženi kartezični in leksikografski produkti grafov. Postavljenih je več odprtih problemov.

Ključne besede

matematika;teorija grafov;razdalja;razdaljno uravnoteženi grafi;produkti grafov;povezanost;mathematics;graph theory;graph distance;distance-balanced graphs;graph products;connectivity;

Podatki

Jezik:	Angleški jezik
Leto izida:	2008
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM PEF - Pedagoška fakulteta
UDK:	519.17
COBISS:	14680153
ISSN:	0218-0006
Št. ogledov:	941
Št. prenosov:	82
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Neznan jezik
Sekundarni naslov:	Razdaljno uravnoteženi grafi
Sekundarni povzetek:	Distance-balanced graphs are introduced as graphs in which every edge $uv$ has the following property: the number of vertices closer to ▫$u$▫ than to ▫$v$▫ is equal to the number of vertices closer to ▫$v$▫ than to ▫$u$▫. Basic properties of these graphs are obtained. The new concept is connected with symmetry conditions in graphs and local operations on graphs are studied with respect to it. Distance-balanced Cartesian and lexicographic products of graphs are also characterized. Several open problems are posed along the way.
Sekundarne ključne besede:	matematika;teorija grafov;razdalja;razdaljno uravnoteženi grafi;produkti grafov;povezanost;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 71-79
Letnik:	ǂVol. ǂ12
Zvezek:	ǂno. ǂ1
Čas izdaje:	2008
ID:	1473563