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


Download (273kB) | Preview


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.

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet
Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Depositing User: Dr. Gábor Wiener
Date Deposited: 28 Sep 2016 14:40
Last Modified: 28 Sep 2016 14:49

Actions (login required)

Edit Item Edit Item