On plane bipartite graphs without fixed edges

Khaled Salem (Avtor), Sandi Klavžar (Avtor)

Povzetek

Povezava grafa ▫$H$▫, ki premore vsaj eno popolno prirejanje, je fiksna povezava, če bodisi pripada vsem popolnim prirejanjem v ▫$H$▫ bodisi nobenemu popolnemu prirejanju. Dokazano je, da je povezan, ravninski, dvodelni graf brez fiksnih povezav natanko tedaj, ko je rob vsakega lica alternirajoči cikel. Nadalje je poliheksagonalen fragment brez fiksnih povezav natanko tedaj, ko so robovi neskončnega lica in vseh nešesterokotniških lic alternirajoči cikli. Dobljeni rezultati predstavljajo razširitev rezultatov iz [F. Zhang, M. Zheng, Generalized hexagonal systems with each hexagon being resonant, Discrete Appl. Math. 36 (1992) 67-73] na posplošene haksagonalne sisteme.

Ključne besede

matematika;teorija grafov;popolno prirejanje;fiksna povezava;alternirajoči cikel;dvodelni ravninski graf;poliheksagonalen fragment;posplošen heksagonalen sistem;mathematics;graph theory;perfect matching;fixed edge;alternating cycle;plane bipartite graph;polyhex fragment;generalized hexagonal system;

Podatki

Jezik:	Angleški jezik
Leto izida:	2007
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FNM - Fakulteta za naravoslovje in matematiko
UDK:	519.17:541
COBISS:	14257753
ISSN:	0893-9659
Št. ogledov:	836
Št. prenosov:	69
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Neznan jezik
Sekundarni naslov:	O ravninskih dvodelnih grafih brez fiksnih povezav
Sekundarni povzetek:	An edge of a graph ▫$H$▫ with a perfect matching is a fixed edge if it either belongs to none or to all of the perfect matchings of ▫$H$▫. It is shown that a connected plane bipartite graph has no fixed edges if and only if the boundary of every face is an alternating cycle. Moreover, a polyhex fragment has no fixed edges if and only if the boundaries of its infinite face and the non-hexagonal finite faces are alternating cycles. These results extend results on generalized hexagonal systems from [F. Zhang, M. Zheng, Generalized hexagonal systems with each hexagon being resonant, Discrete Appl. Math. 36 (1992) 67-73].
Sekundarne ključne besede:	matematika;teorija grafov;popolno prirejanje;fiksna povezava;alternirajoči cikel;dvodelni ravninski graf;poliheksagonalen fragment;posplošen heksagonalen sistem;
URN:	URN:SI:UM:
Vrsta dela (COBISS):	Delo ni kategorizirano
Strani:	str. 813-816
Letnik:	ǂVol. ǂ20
Zvezek:	ǂno. ǂ7
Čas izdaje:	2007
ID:	1473048