On the role of hypercubes in the resonance graphs of benzenoid graphs

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

Abstract

Resonančni graf ▫$R(B)$▫ benzenoidnega grafa ▫$B$▫ ima za točke popolna prirejanja v ▫$B$▫, dve popolni prirejanji sta sosednji, če njuna simetrična razlika tvori množico povezav nekega šestkotnika v ▫$B$▫. Družina ▫$\mathscr{P}$▫ paroma disjunktnih šestkotnikov benzenoidnega grafa ▫$B$▫ je resonančna v $B$, če ▫$B -- \mathscr{P}$▫ vsebuje vsaj eno popolno prirejanje, ali pa je ▫$B -- \mathscr{P}$▫ prazno. Dokazano je, da obstaja surjektivna preslikava ▫$f$▫ iz množice hiperkock grafa ▫$R(B)$▫ na resonančne množice v ▫$B$▫, tako da se ▫$k$▫-dimenzionalna kocka preslika na resonančno množico moči ▫$k$▫.

Keywords

matematika;teorija grafov;benzenoidni graf;popolno prirejanje;resonančni graf;hiperkocka;ne zaključna dela;mathematics;graph theory;benzenoid graph;perfect matching;resonance graph;hypercube;

Data

Language:	English
Year of publishing:	2006
Typology:	1.03 - Short Scientific Article
Organization:	UM PEF - Faculty of Education
UDC:	519.17:541
COBISS:	13943641
ISSN:	0012-365X
Views:	46
Downloads:	26
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	O vlogi hiperkock v resonančnih grafih benzenoidnih grafov
Secondary abstract:	The resonance graph ▫$R(B)$▫ of a benzenoid graph ▫$B$▫ has the perfect matchings of ▫$B$▫ as vertices, two perfect matchings being adjacent if their symmetric difference forms the edge set of a hexagon of ▫$B$▫. A family ▫$\mathscr{P}$▫ of pair-wise disjoint hexagons of a benzenoid graph ▫$B$▫ is resonant in ▫$B$▫ if ▫$B -- \mathscr{P}$▫ contains at least one perfect matching, or if ▫$B -- \mathscr{P}$▫ is empty. It is proven that there exists a surjective map ▫$f$▫ from the set of hypercubes of ▫$R(B)$▫ onto the resonant sets of B such that a ▫$k$▫-dimensional hypercube is mapped into a resonant set of cardinality ▫$k$▫.
Secondary keywords:	Teorija grafov;
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 699-704
Volume:	ǂVol. ǂ306
Issue:	ǂissue ǂ7
Chronology:	2006
DOI:	10.1016/j.disc.2005.11.017
ID:	1472646