错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Cycles of length 3 and 4 in edge-colored complete graphs with restrictions in the color transitions

  • Hortensia Galeana-Sánchez,
  • Felipe Hernández-Lorenzana,
  • Rocío Sánchez-López

摘要

Let G be a graph and H a graph possibly with loops. We will say that a graph G is an H-colored graph if and only if there exists a function \(c:E(G)\longrightarrow V(H)\) c : E ( G ) V ( H ) . A cycle \((v_1,\ldots ,v_k,v_1)\) ( v 1 , , v k , v 1 ) is an H-cycle if and only if \((c(v_1 v_2),\ldots ,c(v_{k-1}v_k),\) ( c ( v 1 v 2 ) , , c ( v k - 1 v k ) , \(c(v_kv_1), c(v_1 v_2))\) c ( v k v 1 ) , c ( v 1 v 2 ) ) is a walk in H. Whenever H is a complete graph without loops, an H-cycle is a properly colored cycle. In this paper, we work with an H-colored complete graph, namely G, with local restrictions given by an auxiliary graph, and we show sufficient conditions implying that every vertex in V(G) is contained in an H-cycle of length 3 (respectively 4). As a consequence, we obtain some well-known results in the theory of properly colored walks.