Hamiltonian-colored powers of strong digraphs

Garry Johns; Ryan Jones; Kyle Kolasinski; Ping Zhang

The search session has expired. Please query the service again.

Displaying similar documents to “Hamiltonian-colored powers of strong digraphs”

An upper bound of a generalized upper Hamiltonian number of a graph

Martin Dzúrik (2021)

Archivum Mathematicum

Similarity:

In this article we study graphs with ordering of vertices, we define a generalization called a pseudoordering, and for a graph $H$ we define the $H$ -Hamiltonian number of a graph $G$ . We will show that this concept is a generalization of both the Hamiltonian number and the traceable number. We will prove equivalent characteristics of an isomorphism of graphs $G$ and $H$ using $H$ -Hamiltonian number of $G$ . Furthermore, we will show that for a fixed number of vertices, each path has a maximal upper...

Spectral radius and Hamiltonicity of graphs with large minimum degree

Vladimir Nikiforov (2016)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a graph of order $n$ and $λ (G)$ the spectral radius of its adjacency matrix. We extend some recent results on sufficient conditions for Hamiltonian paths and cycles in $G$ . One of the main results of the paper is the following theorem: Let $k \geq 2,$ $n \geq k^{3} + k + 4,$ and let $G$ be a graph of order $n$ , with minimum degree $δ (G) \geq k .$ If $λ (G) \geq n - k - 1,$ then $G$ has a Hamiltonian cycle, unless $G = K_{1} \lor (K_{n - k - 1} + K_{k})$ or $G = K_{k} \lor (K_{n - 2 k} + {\bar{K}}_{k}) .$

Hamiltonicity of cubic Cayley graphs

Henry Glover, Dragan Marušič (2007)

Journal of the European Mathematical Society

Similarity:

Following a problem posed by Lovász in 1969, it is believed that every finite connected vertex-transitive graph has a Hamilton path. This is shown here to be true for cubic Cayley graphs arising from finite groups having a $(2, s, 3)$ -presentation, that is, for groups $G = 〈 a, b ∣ a^{2} = 1, b^{s} = 1, {(a b)}^{3} = 1, \dots 〉$ generated by an involution $a$ and an element $b$ of order $s \geq 3$ such that their product $a b$ has order $3$ . More precisely, it is shown that the Cayley graph $X = Cay (G, {a, b, b^{- 1}})$ has a Hamilton cycle when $| G |$ (and thus $s$ ) is congruent to 2 modulo 4, and has a...

Majority choosability of 1-planar digraph

Weihao Xia, Jihui Wang, Jiansheng Cai (2023)

Czechoslovak Mathematical Journal

Similarity:

A majority coloring of a digraph $D$ with $k$ colors is an assignment $π : V (D) \to {1, 2, \dots, k}$ such that for every $v \in V (D)$ we have $π (w) = π (v)$ for at most half of all out-neighbors $w \in N^{+} (v)$ . A digraph $D$ is majority $k$ -choosable if for any assignment of lists of colors of size $k$ to the vertices, there is a majority coloring of $D$ from these lists. We prove that if $U (D)$ is a 1-planar graph without a 4-cycle, then $D$ is majority 3-choosable. And we also prove that every NIC-planar digraph is majority 3-choosable.

On short cycles in triangle-free oriented graphs

Yurong Ji, Shufei Wu, Hui Song (2018)

Czechoslovak Mathematical Journal

Similarity:

An orientation of a simple graph is referred to as an oriented graph. Caccetta and Häggkvist conjectured that any digraph on $n$ vertices with minimum outdegree $d$ contains a directed cycle of length at most $⌈ n / d ⌉$ . In this paper, we consider short cycles in oriented graphs without directed triangles. Suppose that $α_{0}$ is the smallest real such that every $n$ -vertex digraph with minimum outdegree at least $α_{0} n$ contains a directed triangle. Let $ϵ < (3 - 2 α_{0}) / (4 - 2 α_{0})$ be a positive real. We show that if $D$ is an oriented graph...

Self-diclique circulant digraphs

Marietjie Frick, Bernardo Llano, Rita Zuazua (2015)

Mathematica Bohemica

Similarity:

We study a particular digraph dynamical system, the so called digraph diclique operator. Dicliques have frequently appeared in the literature the last years in connection with the construction and analysis of different types of networks, for instance biochemical, neural, ecological, sociological and computer networks among others. Let $D = (V, A)$ be a reflexive digraph (or network). Consider $X$ and $Y$ (not necessarily disjoint) nonempty subsets of vertices (or nodes) of $D$ . A disimplex $K (X, Y)$ of $D$ is...

A note on a conjecture on niche hypergraphs

Pawaton Kaemawichanurat, Thiradet Jiarasuksakun (2019)

Czechoslovak Mathematical Journal

Similarity:

For a digraph $D$ , the niche hypergraph $N ℋ (D)$ of $D$ is the hypergraph having the same set of vertices as $D$ and the set of hyperedges $E (N ℋ (D)) = {e \subseteq V (D) : | e | \geq 2$ and there exists a vertex $v$ such that $e = N_{D}^{-} (v)$ or $e = N_{D}^{+} (v)}$ . A digraph is said to be acyclic if it has no directed cycle as a subdigraph. For a given hypergraph $ℋ$ , the niche number $\hat{n} (ℋ)$ is the smallest integer such that $ℋ$ together with $\hat{n} (ℋ)$ isolated vertices is the niche hypergraph of an acyclic digraph. C. Garske, M. Sonntag and H. M. Teichert (2016) conjectured that for a linear...

Iterated arc graphs

Danny Rorabaugh, Claude Tardif, David Wehlau, Imed Zaguia (2018)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

The arc graph $δ (G)$ of a digraph $G$ is the digraph with the set of arcs of $G$ as vertex-set, where the arcs of $δ (G)$ join consecutive arcs of $G$ . In 1981, S. Poljak and V. Rödl characterized the chromatic number of $δ (G)$ in terms of the chromatic number of $G$ when $G$ is symmetric (i.e., undirected). In contrast, directed graphs with equal chromatic numbers can have arc graphs with distinct chromatic numbers. Even though the arc graph of a symmetric graph is not symmetric, we show that the chromatic number...

Acyclic 4-choosability of planar graphs without 4-cycles

Yingcai Sun, Min Chen (2020)

Czechoslovak Mathematical Journal

Similarity:

A proper vertex coloring of a graph $G$ is acyclic if there is no bicolored cycle in $G$ . In other words, each cycle of $G$ must be colored with at least three colors. Given a list assignment $L = {L (v) : v \in V}$ , if there exists an acyclic coloring $π$ of $G$ such that $π (v) \in L (v)$ for all $v \in V$ , then we say that $G$ is acyclically $L$ -colorable. If $G$ is acyclically $L$ -colorable for any list assignment $L$ with $| L (v) | \geq k$ for all $v \in V$ , then $G$ is acyclically $k$ -choosable. In 2006, Montassier, Raspaud and Wang conjectured that every planar graph without...

The classification of finite groups by using iteration digraphs

Uzma Ahmad, Muqadas Moeen (2016)

Czechoslovak Mathematical Journal

Similarity:

A digraph is associated with a finite group by utilizing the power map $f : G \to G$ defined by $f (x) = x^{k}$ for all $x \in G$ , where $k$ is a fixed natural number. It is denoted by $γ_{G} (n, k)$ . In this paper, the generalized quaternion and $2$ -groups are studied. The height structure is discussed for the generalized quaternion. The necessary and sufficient conditions on a power digraph of a $2$ -group are determined for a $2$ -group to be a generalized quaternion group. Further, the classification of two generated $2$ -groups as abelian...

Neighbor sum distinguishing list total coloring of IC-planar graphs without 5-cycles

Donghan Zhang (2022)

Czechoslovak Mathematical Journal

Similarity:

Let $G = (V (G), E (G))$ be a simple graph and $E_{G} (v)$ denote the set of edges incident with a vertex $v$ . A neighbor sum distinguishing (NSD) total coloring $φ$ of $G$ is a proper total coloring of $G$ such that $\sum_{z \in E_{G} (u) \cup {u}} φ (z) \neq \sum_{z \in E_{G} (v) \cup {v}} φ (z)$ for each edge $u v \in E (G)$ . Pilśniak and Woźniak asserted in 2015 that each graph with maximum degree $Δ$ admits an NSD total $(Δ + 3)$ -coloring. We prove that the list version of this conjecture holds for any IC-planar graph with $Δ \geq 11$ but without $5$ -cycles by applying the Combinatorial Nullstellensatz.