On short cycles in triangle-free oriented graphs

Yurong Ji; Shufei Wu; Hui Song

Displaying similar documents to “On short cycles in triangle-free oriented graphs”

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 Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths

Halina Bielak, Kinga Dąbrowska (2015)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

The Ramsey number $R (G, H)$ for a pair of graphs $G$ and $H$ is defined as the smallest integer $n$ such that, for any graph $F$ on $n$ vertices, either $F$ contains $G$ or $\bar{F}$ contains $H$ as a subgraph, where $\bar{F}$ denotes the complement of $F$ . We study Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths and determine these numbers for some cases. We extend many known results studied in [5, 14, 18, 19, 20]. In particular we count the numbers $R (K_{1} + L_{n}, P_{m})$ and $R (K_{1} + L_{n}, C_{m})$ for some integers $m$ , $n$ , where $L_{n}$ is...

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...

Degree sums of adjacent vertices for traceability of claw-free graphs

Tao Tian, Liming Xiong, Zhi-Hong Chen, Shipeng Wang (2022)

Czechoslovak Mathematical Journal

Similarity:

The line graph of a graph $G$ , denoted by $L (G)$ , has $E (G)$ as its vertex set, where two vertices in $L (G)$ are adjacent if and only if the corresponding edges in $G$ have a vertex in common. For a graph $H$ , define ${\bar{σ}}_{2} (H) = min {d (u) + d (v) : u v \in E (H)}$ . Let $H$ be a 2-connected claw-free simple graph of order $n$ with $δ (H) \geq 3$ . We show that, if ${\bar{σ}}_{2} (H) \geq \frac{1}{7} (2 n - 5)$ and $n$ is sufficiently large, then either $H$ is traceable or the Ryjáček’s closure $cl (H) = L (G)$ , where $G$ is an essentially $2$ -edge-connected triangle-free graph that can be contracted to one of the two graphs of order 10...

On the tree structure of the power digraphs modulo $n$

Amplify Sawkmie, Madan Mohan Singh (2015)

Czechoslovak Mathematical Journal

Similarity:

For any two positive integers $n$ and $k \geq 2$ , let $G (n, k)$ be a digraph whose set of vertices is ${0, 1, ..., n - 1}$ and such that there is a directed edge from a vertex $a$ to a vertex $b$ if $a^{k} \equiv b (mod n)$ . Let $n = \prod_{i = 1}^{r} p_{i}^{e_{i}}$ be the prime factorization of $n$ . Let $P$ be the set of all primes dividing $n$ and let $P_{1}, P_{2} \subseteq P$ be such that $P_{1} \cup P_{2} = P$ and $P_{1} \cap P_{2} = \emptyset$ . A fundamental constituent of $G (n, k)$ , denoted by $G_{P_{2}}^{*} (n, k)$ , is a subdigraph of $G (n, k)$ induced on the set of vertices which are multiples of $\prod_{p_{i} \in P_{2}} p_{i}$ and are relatively prime to all primes $q \in P_{1}$ . L. Somer and M. Křížek proved that the trees attached...

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...

The Turán number of the graph $3 P_{4}$

Halina Bielak, Sebastian Kieliszek (2014)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

Let $e x (n, G)$ denote the maximum number of edges in a graph on $n$ vertices which does not contain $G$ as a subgraph. Let $P_{i}$ denote a path consisting of $i$ vertices and let $m P_{i}$ denote $m$ disjoint copies of $P_{i}$ . In this paper we count $e x (n, 3 P_{4})$ .

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.

Saturation numbers for linear forests $P_{6} + t P_{2}$

Jingru Yan (2023)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is $H$ -saturated if it contains no $H$ as a subgraph, but does contain $H$ after the addition of any edge in the complement of $G$ . The saturation number, $sat (n, H)$ , is the minimum number of edges of a graph in the set of all $H$ -saturated graphs of order $n$ . We determine the saturation number $sat (n, P_{6} + t P_{2})$ for $n \geq \frac{10}{3} t + 10$ and characterize the extremal graphs for $n > \frac{10}{3} t + 20$ .

Even factor of bridgeless graphs containing two specified edges

Nastaran Haghparast, Dariush Kiani (2018)

Czechoslovak Mathematical Journal

Similarity:

An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Let $G$ be a bridgeless simple graph with minimum degree at least $3$ . Jackson and Yoshimoto (2007) showed that $G$ has an even factor containing two arbitrary prescribed edges. They also proved that $G$ has an even factor in which each component has order at least four. Moreover, Xiong, Lu and Han (2009) showed that for each pair of edges $e_{1}$ and $e_{2}$ of $G$ , there is an even factor containing $e_{1}$ and $e_{2}$ ...

Characterizing finite groups whose enhanced power graphs have universal vertices

David G. Costanzo, Mark L. Lewis, Stefano Schmidt, Eyob Tsegaye, Gabe Udell (2024)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a finite group and construct a graph $Δ (G)$ by taking $G ∖ {1}$ as the vertex set of $Δ (G)$ and by drawing an edge between two vertices $x$ and $y$ if $〈 x, y 〉$ is cyclic. Let $K (G)$ be the set consisting of the universal vertices of $Δ (G)$ along the identity element. For a solvable group $G$ , we present a necessary and sufficient condition for $K (G)$ to be nontrivial. We also develop a connection between $Δ (G)$ and $K (G)$ when $| G |$ is divisible by two distinct primes and the diameter of $Δ (G)$ is 2.

The small Ree group $^{2} G_{2} (3^{2 n + 1})$ and related graph

Alireza K. Asboei, Seyed S. S. Amiri (2018)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

Let $G$ be a finite group. The main supergraph $𝒮 (G)$ is a graph with vertex set $G$ in which two vertices $x$ and $y$ are adjacent if and only if $o (x) ∣ o (y)$ or $o (y) ∣ o (x)$ . In this paper, we will show that $G ≅^{2} G_{2} (3^{2 n + 1})$ if and only if $𝒮 (G) ≅ 𝒮 (^{2} G_{2} (3^{2 n + 1}))$ . As a main consequence of our result we conclude that Thompson’s problem is true for the small Ree group $^{2} G_{2} (3^{2 n + 1})$ .

Resolving sets of directed Cayley graphs for the direct product of cyclic groups

Demelash Ashagrie Mengesha, Tomáš Vetrík (2019)

Czechoslovak Mathematical Journal

Similarity:

A directed Cayley graph $C (Γ, X)$ is specified by a group $Γ$ and an identity-free generating set $X$ for this group. Vertices of $C (Γ, X)$ are elements of $Γ$ and there is a directed edge from the vertex $u$ to the vertex $v$ in $C (Γ, X)$ if and only if there is a generator $x \in X$ such that $u x = v$ . We study graphs $C (Γ, X)$ for the direct product $Z_{m} \times Z_{n}$ of two cyclic groups $Z_{m}$ and $Z_{n}$ , and the generating set $X = {(0, 1), (1, 0), (2, 0), \dots, (p, 0)}$ . We present resolving sets which yield upper bounds on the metric dimension of these graphs for $p = 2$ and $3$ .

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...