Please use this identifier to cite or link to this item:
|Title:||Graph structural properties of non-Yutsis graphs allowing fast recognition||Authors:||Aldred, Robert E. L.
VAN DYCK, Dries
McKay, Brendan D.
|Issue Date:||2009||Publisher:||ELSEVIER SCIENCE BV||Source:||DISCRETE APPLIED MATHEMATICS, 157(2). p. 377-386||Abstract:||Yutsis 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.||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.||Keywords:||Yutsis graph; Dual Hamiltonian graph; Decision problem; General recoupling coefficient||Document URI:||http://hdl.handle.net/1942/9184||ISSN:||0166-218X||e-ISSN:||1872-6771||DOI:||10.1016/j.dam.2008.03.020||ISI #:||000262017600018||Category:||A1||Type:||Journal Contribution||Validations:||ecoom 2010|
|Appears in Collections:||Research publications|
Show full item record
checked on Sep 3, 2020
WEB OF SCIENCETM
checked on May 21, 2022
checked on May 20, 2022
checked on May 20, 2022
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.