On plane bipartite graphs without fixed edges

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

Abstract

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.

Keywords

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;

Data

Language:	English
Year of publishing:	2007
Typology:	1.01 - Original Scientific Article
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
UDC:	519.17:541
COBISS:	14257753
ISSN:	0893-9659
Views:	836
Downloads:	69
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Unknown
Secondary title:	O ravninskih dvodelnih grafih brez fiksnih povezav
Secondary abstract:	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].
Secondary keywords:	matematika;teorija grafov;popolno prirejanje;fiksna povezava;alternirajoči cikel;dvodelni ravninski graf;poliheksagonalen fragment;posplošen heksagonalen sistem;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 813-816
Volume:	ǂVol. ǂ20
Issue:	ǂno. ǂ7
Chronology:	2007
ID:	1473048