Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/9184
Full metadata record
DC FieldValueLanguage
dc.contributor.authorAldred, Robert E. L.-
dc.contributor.authorVAN DYCK, Dries-
dc.contributor.authorBrinkmann, Gunnar-
dc.contributor.authorFack, Veerle-
dc.contributor.authorMcKay, Brendan D.-
dc.date.accessioned2009-01-19T10:27:29Z-
dc.date.available2009-01-19T10:27:29Z-
dc.date.issued2009-
dc.identifier.citationDISCRETE APPLIED MATHEMATICS, 157(2). p. 377-386-
dc.identifier.issn0166-218X-
dc.identifier.urihttp://hdl.handle.net/1942/9184-
dc.description.abstractYutsis graphs are connected simple graphs which can be partitioned into two vertex-induced trees. Cubic Yutsis graphs were introduced by Jaeger as cubic dual Hamiltonian graphs, and these are our main focus. Cubic Yutsis graphs also appear in the context of the quantum theory of angular momenta, where they are used to generate summation formulae for general recoupling coefficients. Large Yutsis graphs are of interest for benchmarking algorithms which generate these formulae. In an earlier paper we showed that the decision problem of whether a given cubic graph is Yutsis is NP-complete. We also described a heuristic that was tested on graphs with up to 300,000 vertices and found Yutsis decompositions for all large Yutsis graphs very quickly. In contrast, no fast technique was known by which a significant fraction of bridgeless non-Yutsis cubic graphs could be shown to be non-Yutsis. One of the contributions of this article is to describe some structural impediments to Yutsisness. We also provide experimental evidence that almost all non-Yutsis cubic graphs can be rapidly shown to be non-Yutsis by applying a heuristic based on some of these criteria. Combined with the algorithm described in the earlier paper this gives an algorithm that, according to experimental evidence, runs efficiently on practically every large random cubic graph and can decide on whether the graph is Yutsis or not. The second contribution of this article is a set of construction techniques for non-Yutsis graphs implying, for example, the existence of 3-connected non-Yutsis cubic graphs of arbitrary girth and with few non-trivial 3-cuts. (C) 2008 Elsevier B.V. All rights reserved.-
dc.language.isoen-
dc.publisherELSEVIER SCIENCE BV-
dc.subject.otherYutsis graph; Dual Hamiltonian graph; Decision problem; General recoupling coefficient-
dc.titleGraph structural properties of non-Yutsis graphs allowing fast recognition-
dc.typeJournal Contribution-
dc.identifier.epage386-
dc.identifier.issue2-
dc.identifier.spage377-
dc.identifier.volume157-
local.format.pages10-
local.bibliographicCitation.jcatA1-
dc.description.notes[Brinkmann, Gunnar; Fack, Veerle] Univ Ghent, Dept Appl Math & Comp Sci, B-9000 Ghent, Belgium. [McKay, Brendan D.] Australian Natl Univ, Dept Comp Sci, Canberra, ACT 0200, Australia. [Aldred, Robert E. L.] Univ Otago, Dept Math, Dunedin, New Zealand. [Van Dyck, Dries] Transnat Univ Limburg, Hasselt Univ, Dept Math Phys & Comp Sci, B-3590 Diepenbeek, Belgium.-
local.type.refereedRefereed-
local.type.specifiedArticle-
dc.bibliographicCitation.oldjcatA1-
dc.identifier.doi10.1016/j.dam.2008.03.020-
dc.identifier.isi000262017600018-
item.fulltextWith Fulltext-
item.fullcitationAldred, Robert E. L.; VAN DYCK, Dries; Brinkmann, Gunnar; Fack, Veerle & McKay, Brendan D. (2009) Graph structural properties of non-Yutsis graphs allowing fast recognition. In: DISCRETE APPLIED MATHEMATICS, 157(2). p. 377-386.-
item.contributorAldred, Robert E. L.-
item.contributorVAN DYCK, Dries-
item.contributorBrinkmann, Gunnar-
item.contributorFack, Veerle-
item.contributorMcKay, Brendan D.-
item.validationecoom 2010-
item.accessRightsOpen Access-
crisitem.journal.issn0166-218X-
crisitem.journal.eissn1872-6771-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
graph.pdfNon Peer-reviewed author version205.28 kBAdobe PDFView/Open
Show simple item record

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.