We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
H-Cycles in H-Colored Multigraphs.
- Authors
Galeana-Sánchez, Hortensia; Rojas-Monroy, Rocío; Sánchez-López, Rocío; Villarreal-Valdés, Juana Imelda
- Abstract
Let H be a graph possibly with loops and G a multigraph without loops. G is said to be H-colored if there exists a function c: E(G) → V(H). A cycle ( v 0 , e 0 , v 1 , e 1 , ... , e k - 1 , v k = v 0 ) in G, where e i = v i v i + 1 for every i in {0, ... , k - 1 }, is an H-cycle if and only if (c( e 0 ), a 0 , c( e 1 ), ... , c( e k - 2 ), a k - 2 , c( e k - 1 ), a k - 1 , c( e 0 )) is a walk in H, with a i = c( e i )c( e i + 1 ) for every i in {0, ... , k - 1 } (indices modulo k). If H is a complete graph without loops, an H-walk is called properly colored walk. The problem of check whether an edge-colored graph G contains a properly colored cycle was studied first by Grossman and Häggkvist. Subsequently Yeo gave a sufficient condition which guarantee the existence of a properly colored cycle. In this paper we will extend Yeo's result for the case where stronger requirements are enforced for a properly colored cycle to be eligible, based on the adjacencies of a graph whose vertices are in bijection with the colors. The main result establishes that if H is a graph without loops and G is an H-colored multigraph such that (1) H and G have no isolated vertices, (2) G has no H-cycles and (3) for every x in V(G), G x is a complete k x -partite graph for some k x in N . Then there exists a vertex z in V(G) such that every connected component D of G - z satisfies that {e ∈ E(G) : e = z u for some u in V(D)} is an independent set in G z (where for w in V(G), G w is an associated graph to the vertex w, respect to the H-coloring of G).
- Subjects
MULTIGRAPH; INDEPENDENT sets; COMPLETE graphs; BIJECTIONS
- Publication
Graphs & Combinatorics, 2022, Vol 38, Issue 3, p1
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-022-02464-4