Spanning trails containing given edges

Weiqi Luo; Zhi-Hong Chen; Wei-Guo Chen

doi:10.1016/j.disc.2005.10.022

Spanning trails containing given edges

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

Research output: Contribution to journal › Article › peer-review

Abstract

<p> A graph G is Eulerian-connected if for any u and v in V ( G ) , G has a spanning ( u , v ) -trail. A graph G is edge-Eulerian-connected if for any e ′ and e ″ in E ( G ) , G has a spanning ( e ′ , e ″ ) -trail. For an integer r &ges; 0 , a graph is called r -Eulerian-connected if for any X &sube; E ( G ) with | X | &les; r , and for any u , v ∈ V ( G ) , G has a spanning ( u , v ) -trail T such that X &sube; E ( T ) . The r -edge-Eulerian-connectivity of a graph can be defined similarly. Let θ ( r ) be the minimum value of k such that every k -edge-connected graph is r -Eulerian-connected. Catlin proved that θ ( 0 ) = 4 . We shall show that θ ( r ) = 4 for 0 &les; r &les; 2 , and θ ( r ) = r + 1 for r &ges; 3 . Results on r -edge-Eulerian connectivity are also discussed.</p>

Original language	American English
Journal	Scholarship and Professional Work - LAS
Volume	306
Issue number	1
DOIs	https://doi.org/10.1016/j.disc.2005.10.022
State	Published - Jan 1 2006

Keywords

Collapsible graphs
Connectivity
Spanning trails
Supereulerian graphs

Disciplines

Computer Sciences
Mathematics

Access to Document

10.1016/j.disc.2005.10.022License: Unspecified

Spanning trails containing given edgesFinal published version, 551 KBLicense: Unspecified

Cite this

@article{c51e7d265a014f06b3c87698482d0048,

title = "Spanning trails containing given edges",

abstract = " A graph G is Eulerian-connected if for any u and v in V ( G ) , G has a spanning ( u , v ) -trail. A graph G is edge-Eulerian-connected if for any e ′ and e ″ in E ( G ) , G has a spanning ( e ′ , e ″ ) -trail. For an integer r &ges; 0 , a graph is called r -Eulerian-connected if for any X &sube; E ( G ) with | X | &les; r , and for any u , v ∈ V ( G ) , G has a spanning ( u , v ) -trail T such that X &sube; E ( T ) . The r -edge-Eulerian-connectivity of a graph can be defined similarly. Let θ ( r ) be the minimum value of k such that every k -edge-connected graph is r -Eulerian-connected. Catlin proved that θ ( 0 ) = 4 . We shall show that θ ( r ) = 4 for 0 &les; r &les; 2 , and θ ( r ) = r + 1 for r &ges; 3 . Results on r -edge-Eulerian connectivity are also discussed.",

keywords = "Collapsible graphs, Connectivity, Spanning trails, Supereulerian graphs",

author = "Weiqi Luo and Zhi-Hong Chen and Wei-Guo Chen",

year = "2006",

month = jan,

day = "1",

doi = "10.1016/j.disc.2005.10.022",

language = "American English",

volume = "306",

journal = "Scholarship and Professional Work - LAS",

number = "1",

}

TY - JOUR

T1 - Spanning trails containing given edges

AU - Luo, Weiqi

AU - Chen, Zhi-Hong

AU - Chen, Wei-Guo

PY - 2006/1/1

Y1 - 2006/1/1

N2 - A graph G is Eulerian-connected if for any u and v in V ( G ) , G has a spanning ( u , v ) -trail. A graph G is edge-Eulerian-connected if for any e ′ and e ″ in E ( G ) , G has a spanning ( e ′ , e ″ ) -trail. For an integer r &ges; 0 , a graph is called r -Eulerian-connected if for any X &sube; E ( G ) with | X | &les; r , and for any u , v ∈ V ( G ) , G has a spanning ( u , v ) -trail T such that X &sube; E ( T ) . The r -edge-Eulerian-connectivity of a graph can be defined similarly. Let θ ( r ) be the minimum value of k such that every k -edge-connected graph is r -Eulerian-connected. Catlin proved that θ ( 0 ) = 4 . We shall show that θ ( r ) = 4 for 0 &les; r &les; 2 , and θ ( r ) = r + 1 for r &ges; 3 . Results on r -edge-Eulerian connectivity are also discussed.

AB - A graph G is Eulerian-connected if for any u and v in V ( G ) , G has a spanning ( u , v ) -trail. A graph G is edge-Eulerian-connected if for any e ′ and e ″ in E ( G ) , G has a spanning ( e ′ , e ″ ) -trail. For an integer r &ges; 0 , a graph is called r -Eulerian-connected if for any X &sube; E ( G ) with | X | &les; r , and for any u , v ∈ V ( G ) , G has a spanning ( u , v ) -trail T such that X &sube; E ( T ) . The r -edge-Eulerian-connectivity of a graph can be defined similarly. Let θ ( r ) be the minimum value of k such that every k -edge-connected graph is r -Eulerian-connected. Catlin proved that θ ( 0 ) = 4 . We shall show that θ ( r ) = 4 for 0 &les; r &les; 2 , and θ ( r ) = r + 1 for r &ges; 3 . Results on r -edge-Eulerian connectivity are also discussed.

KW - Collapsible graphs

KW - Connectivity

KW - Spanning trails

KW - Supereulerian graphs

UR - https://digitalcommons.butler.edu/facsch_papers/142

U2 - 10.1016/j.disc.2005.10.022

DO - 10.1016/j.disc.2005.10.022

M3 - Article

VL - 306

JO - Scholarship and Professional Work - LAS

JF - Scholarship and Professional Work - LAS

IS - 1

ER -

Spanning trails containing given edges

Abstract

Keywords

Disciplines

Access to Document

Other files and links

Cite this