Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/9184

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
Citation: 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.
URI: http://hdl.handle.net/1942/9184
DOI: 10.1016/j.dam.2008.03.020
ISI #: 000262017600018
ISSN: 0166-218X
Category: A1
Type: Journal Contribution
Validation: ecoom, 2010
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Preprint205.28 kBAdobe PDF

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