Spanning trails containing given edges

DOI10.1016/J.DISC.2005.10.022MaRDI QIDQ817757zbMATH OpenOpenAlexFDO

Authors Weiqi Luo, Zhi-Hong Chen, Wei-Guo Chen

Publication date 20 March 2006

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://digitalcommons.butler.edu/cgi/viewcontent.cgi?article=1144&context=facsch_papers

zbMATH Keywords

Eulerian connectivity

Mathematics Subject Classification ID

Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)

Review text

Let \(r\geq 0\) be an integer. A graph \(G\) is called \(r\)-Eulerian-connected if for any \(X\subseteq E(G)\) with \(| X| \leq r\) and for any two vertices \(u,v\in V(G)\) (including the case \(u=v\)), the graph \(G\) has a spanning \((u,v)\)-trail containing all edges of \(X\), and \(G\) is called \(r\)-edge-Eulerian-connected if for any \(X\subseteq E(G)\) with \(| X| \leq r\) and for any two different edges \(e',e\in E(G)\), the graph \(G\) has a spanning \((e',e)\)-trail containing all edges of \(X\). Let \(\theta(r)\) be the minimum value of \(k\) such that each \(k\)-edge-connected graph is \(r\)-Eulerian-connected. Catlin proved that \(\theta(0)=4\). In this paper the authors show that \(\theta(r)=4\) for \(0\leq r\leq 2\) and \(\theta(r)=r+1\) for \(r\geq 3\). Results on \(r\)-edge-Eulerian-connected graphs are also presented.

Recommendations

Cites work

Cited in

(15)

This page was built for publication: Spanning trails containing given edges

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q817757)