NDLI: H-Paths and H-Cycles in H-Coloured Digraphs

Content Provider	Springer Nature Link
Author	Galeana Sánchez, Hortensia Torres Ramos, Ingrid
Copyright Year	2013
Abstract	A digraph D is a strongly transitive digraph if for any vertices $${u, v, w \in V(D)}$$ (possibly u = w) such that $${\{(u, v), (v, w)\} \subseteq A(D)}$$ implies $${(u, w) \in A(D)}$$ (when u = w and $${\{(u, v), (v, w)\} \subseteq A(D)}$$ then $${\{(u, u), (v, v)\} \subseteq A(D)}$$ ). Let H be a strongly transitive digraph (possibly with loops) and D a digraph(that contains neither loops nor multiple arcs). A digraph D is said to be H-coloured if the arcs of D are coloured with the vertices of H. Will be denoted by c(x, y) the color of the arc $${(x, y)\in A(D)}$$ . A directed walk(directed path) $${C=(z_{0}, z_{1}, \ldots, z_{t})}$$ in D will be called an H-walk(path) in D if $${(c(z_{0}, z_{1}), c(z_{1}, z_{2}), \ldots, c(z_{t-1}, z_{t}))}$$ is a directed walk in H. Let D 1 and D 2 be spanning subdigraphs of D. A succession [u, v, w, u] is a (D 1, D, D 2) H-subdivision of C 3, if there exist: T 1 an H-path from u to v contained in D 1, T an H-path from v to w in D, T 2 an H-path from w to u contained in D 2; and these path satisfies: (1) (c(final arc of T 1), c(initial arc of T)) $${\notin A(H)}$$ , (c(final arc of T), c(initial arc of T 2)) $${\notin A(H)}$$ and (c(final arc of T 2), c(initial arc of T 1)) $${\notin A(H)}$$ ; (2) $${T_{1} \bigcup T\bigcup T_{2}}$$ is a cycle in D. A succession [u, v, w, x ] is a (D 1, D, D 2) H-subdivision of P 3, if there exist: T 1 an H-path from u to v contained in D 1, T an H-path from v to w in D, T 2 an H-path from w to x contained in D 2; such that (1) (c(final arc of T 1), c(initial arc of T)) $${\notin A(H)}$$ and (c(final arc of T), c(initial arc of T 2)) $${\notin A(H)}$$ ; (2) $${T_{1} \bigcup T\bigcup T_{2}}$$ is a path in D. Let H be a strongly transitive digraph and D an H-coloured digraph. Let D 1 and D 2 be spanning subdigraphs of D. Will be said that P = {D 1, D 2} is an H-separation of D if: (1) $${A(D_{1}) \bigcap A(D_{2})= \emptyset, A(D_{1}) \bigcup A(D_{2}) = A(D)}$$ ; (2) every H-path of D is contained in D 1 or it is contained in D 2. In this paper will be proved that: if H is a strongly transitive digraph and D is an H-coloured digraph, P = {D 1, D 2} an H-separation of D such that: (1) every cycle of D that is contained in D i is an H-cycle for $${i\in \{1, 2\}}$$ ; (2) D does not contain a (D 1, D, D 2) H-subdivision of C 3; (3) if (u, z, w, x 0) is a (D 1, D, D 2) H-subdivision of P 3 then there exists some H-path between u and x 0. Then D has an H-kernel by paths.
Ending Page	628
Page Count	14
Starting Page	615
File Format	PDF
ISSN	09110119
e-ISSN	14355914
Journal	Graphs and Combinatorics
Issue Number	3
Volume Number	31
Language	English
Publisher	Springer Japan
Publisher Date	2014-01-04
Publisher Place	Tokyo
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	H-semikernel by paths mod D 1 H-subdivision of P 3 H-separation H-coloured digraph H-kernel by paths H-subdivision of C 3 Directed graphs (digraphs), tournaments Engineering Design Combinatorics Kernel
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Theoretical Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Richardson’s Theorem in H-coloured Digraphs

Monochromatic Paths and at Most 2-Coloured Arc Sets in Edge-Coloured Tournaments

H-Kernels in Infinite Digraphs

An Extension of Richardson’s Theorem in m-Colored Digraphs

A Degree Sum Condition for Hamiltonicity in Balanced Bipartite Digraphs

On d-arc-dominated Oriented Graphs

Almost Symmetric Cycles in Large Digraphs

Cycles and p-competition graphs

Cycles in Oriented 3-Graphs

H-Paths and H-Cycles in H-Coloured Digraphs

Similar Documents

Richardson’s Theorem in H-coloured Digraphs

Monochromatic Paths and at Most 2-Coloured Arc Sets in Edge-Coloured Tournaments

H-Kernels in Infinite Digraphs

An Extension of Richardson’s Theorem in m-Colored Digraphs

A Degree Sum Condition for Hamiltonicity in Balanced Bipartite Digraphs

On d-arc-dominated Oriented Graphs

Almost Symmetric Cycles in Large Digraphs

Cycles and p-competition graphs

Cycles in Oriented 3-Graphs

H-Paths and H-Cycles in H-Coloured Digraphs