文献

J-GLOBAL ID：202202290772394286   整理番号：22A0764321

H-彩色マルチグラフでのH-サイクル

H-Cycles in H-Colored Multigraphs

著者 (4件)： Galeana-Sanchez Hortensia (Instituto de Matematicas, Universidad Nacional Autonoma de Mexico, Coyoacan, CDMX, Mexico) ,  Rojas-Monroy Rocio (Facultad de Ciencias, Universidad Autonoma del Estado de Mexico, Toluca, Edo. de Mexico, Mexico) ,  Sanchez-Lopez Rocio (Facultad de Ciencias, Universidad Nacional Autonoma de Mexico, Coyoacan, CDMX, Mexico) ,  Villarreal-Valdes Juana Imelda (Facultad de Ciencias, Universidad Autonoma del Estado de Mexico, Toluca, Edo. de Mexico, Mexico)
資料名： Graphs and Combinatorics (Web)  (Graphs and Combinatorics (Web))
巻： 38  号： 3  ページ： 62  発行年： 2022年 
JST資料番号： U1590A  ISSN： 0911-0119  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： Hをループを持つ可能性のあるグラフ,Gをループのないマルチグラフとする。関数c:E(G)→V(H)が存在する時,GはH-彩色であると言う。{0,...,k-1}(モジュロkを示す)内の全てのiについてa_i=c(e_i)c(e_i+1)となるような(c(e₀),a₀,c(e₁),...,c(e_k-2)a_k-2,c(e_k-1),a_k-1,c(e₀))がH内でのウォークである時に限り,{0,...,k-1}内の全てのiについてe_i=v_iv_i+1となるようなG内のサイクル(v₀,e₀,v₁,e₁,...e_k-1,v_k=v₀)がH-サイクルである。Hがループのない完全グラフならば,H-ウォークは適切な彩色ウォークであると言う。辺彩色グラフGが適切な彩色サイクルを含むか否かを確認する問題は,GrossmanとHaggkvistにより最初に研究された。続いてYeoが適切な彩色サイクルが存在することを保証する十分条件を与えた。本論文では,頂点が色と全単射であるグラフの隣接性に基づきより強い要件が適切な彩色サイクルを適格にさせるようにする事例についてYeoの結果を拡張する。主要な結果は,Hがループのないグラフで,(1)HとGが孤立頂点を持たない,(2)GがH-サイクルを持たない及び(3)V(G)内の全てのxについてG_xがN内のあるk_xについて完全k_x-二部グラフであるようにGがH-彩色マルチグラフであるか否かを確立した。その後で,G-zの全ての連結成分Dが{e∈E(G):V(D)内のあるuについてe=zu}がG_z内の独立集合(ここでV(G)内のwについてG_w)はGのH-彩色に関する頂点wの関連グラフ)であることを満たすようなV(G)内の頂点zが存在する。Copyright The Author(s), under exclusive licence to Springer Japan KK, part of Springer Nature 2022 Translated from English into Japanese by JST.

シソーラス用語： 写像 ,  部分グラフ ,  *サイクル ,  *彩色問題 ,  *ループ ,  完全グラフ ,  頂点 ,  端部 ,  定理証明 ,  理論 ,  集合 ,  歩行
準シソーラス用語： ウォーク ,  エッジ ,  *グラフ彩色 ,  二部グラフ ,  仮説 ,  全単射 ,  辺 ,  隣接関係

著者キーワード (4件)： H経路 ,  H彩色マルチグラフ ,  交代サイクル ,  Hサイクル

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (4件)： 彩色 ,  マルチ ,  グラフ ,  サイクル