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 
Brinkmann, Gunnar
Fack, Veerle
McKay, Brendan D.
Issue Date: 2009
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:
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

Files in This Item:
File Description SizeFormat 
graph.pdfPreprint205.28 kBAdobe PDFView/Open
Show full item record


checked on Sep 3, 2020


checked on May 21, 2022

Page view(s)

checked on May 20, 2022


checked on May 20, 2022

Google ScholarTM



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