Wiener, Gábor (2016) On nontraceable, nonhypotraceable, arachnoid graphs. ELECTRONIC NOTES IN DISCRETE MATHEMATICS, 49. pp. 621627. ISSN 15710653

Text
eurocomb15wiener.pdf Download (267Kb)  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 (nontraceable graphs with the property that all vertexdeleted 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 nontraceable, nonhypotraceable, arachnoid graph that contains H as an induced subgraph.
Item Type:  Article 

Subjects:  Q Science / természettudomány > QA Mathematics / matematika > QA166QA166.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 
URI:  http://real.mtak.hu/id/eprint/40393 
Actions (login required)
View Item 