On non-traceable, non-hypotraceable, arachnoid graphs

Wiener, Gábor (2016) On non-traceable, non-hypotraceable, arachnoid graphs. ELECTRONIC NOTES IN DISCRETE MATHEMATICS, 49. pp. 621-627. ISSN 1571-0653

Preview

Text eurocomb15wiener.pdf Download (273kB) | Preview

Abstract

Motivated by questions concerning optical networks, in 2003 Gargano, Hammar, Hell, Stacho, and Vaccaro defined the notions of spanning spiders and arachnoid graphs. A spider is a tree with at most one branch (vertex of degree at least 3). The spider is centred at the branch vertex (if there is any,otherwise it is centred at any of the vertices). A graph is arachnoid if it has a spanning spider centred at any of its vertices. Traceable graphs are obviously arachnoid, and Gargano et al. observed that hypotraceable graphs (non-traceable graphs with the property that all vertex-deleted subgraphs are traceable) are also easily seen to be arachnoid. However, they did not find any other arachnoid graphs, and asked the question whether they exist. The main goal of this paper is to answer this question in the affirmative, moreover, we show that for any prescribed graph H, there exists a non-traceable, non-hypotraceable, arachnoid graph that contains H as an induced subgraph.

Actions (login required)

Edit Item