Pairs of forbidden class of subgraphs concerning $K_{1,3}$ and P₆ to have a cycle containing specified vertices

Takeshi Sugiyama; Masao Tsugaki

Displaying similar documents to “Pairs of forbidden class of subgraphs concerning $K_{1, 3}$ and P₆ to have a cycle containing specified vertices”

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

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

On-line ranking number for cycles and paths

Erik Bruoth, Mirko Horňák (1999)

Discussiones Mathematicae Graph Theory

Similarity:

A k-ranking of a graph G is a colouring φ:V(G) → 1,...,k such that any path in G with endvertices x,y fulfilling φ(x) = φ(y) contains an internal vertex z with φ(z) > φ(x). On-line ranking number $χ *_{r} (G)$ of a graph G is a minimum k such that G has a k-ranking constructed step by step if vertices of G are coming and coloured one by one in an arbitrary order; when colouring a vertex, only edges between already present vertices are known. Schiermeyer, Tuza and Voigt proved that $χ *_{r} (P ₙ) < 3 l o g ₂ n$ for n ≥ 2....

The extremal irregularity of connected graphs with given number of pendant vertices

Xiaoqian Liu, Xiaodan Chen, Junli Hu, Qiuyun Zhu (2022)

Czechoslovak Mathematical Journal

Similarity:

The irregularity of a graph $G = (V, E)$ is defined as the sum of imbalances $| d_{u} - d_{v} |$ over all edges $u v \in E$ , where $d_{u}$ denotes the degree of the vertex $u$ in $G$ . This graph invariant, introduced by Albertson in 1997, is a measure of the defect of regularity of a graph. In this paper, we completely determine the extremal values of the irregularity of connected graphs with $n$ vertices and $p$ pendant vertices ( $1 \leq p \leq n - 1$ ), and characterize the corresponding extremal graphs.

On the order of certain close to regular graphs without a matching of given size

Sabine Klinkenberg, Lutz Volkmann (2007)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is a ${d, d + k}$ -graph, if one vertex has degree $d + k$ and the remaining vertices of $G$ have degree $d$ . In the special case of $k = 0$ , the graph $G$ is $d$ -regular. Let $k, p \geq 0$ and $d, n \geq 1$ be integers such that $n$ and $p$ are of the same parity. If $G$ is a connected ${d, d + k}$ -graph of order $n$ without a matching $M$ of size $2 | M | = n - p$ , then we show in this paper the following: If $d = 2$ , then $k \geq 2 (p + 2)$ and (i) $n \geq k + p + 6$ . If $d \geq 3$ is odd and $t$ an integer with $1 \leq t \leq p + 2$ , then (ii) $n \geq d + k + 1$ for $k \geq d (p + 2)$ , (iii) $n \geq d (p + 3) + 2 t + 1$ for $d (p + 2 - t) + t \leq k \leq d (p + 3 - t) + t - 3$ , (iv) $n \geq d (p + 3) + 2 p + 7$ for $k \leq p$ . If $d \geq 4$ is even, then (v) $n \geq d + k + 2 - η$ for $k \geq d (p + 3) + p + 4 + η$ , (vi) $n \geq d + k + p + 2 - 2 t = d (p + 4) + p + 6$ for $k = d (p + 3) + 4 + 2 t$ and $p \geq 1$ ,...

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

Proper connection number of bipartite graphs

Jun Yue, Meiqin Wei, Yan Zhao (2018)

Czechoslovak Mathematical Journal

Similarity:

An edge-colored graph $G$ is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph $G$ , denoted by $pc (G)$ , is the smallest number of colors that are needed to color the edges of $G$ in order to make it proper connected. In this paper, we obtain the sharp upper bound for $pc (G)$ of a general bipartite graph $G$ and a series of extremal graphs. Additionally, we give a proper $2$ -coloring for a connected bipartite graph $G$ having $δ (G) \geq 2$ and a dominating...

On arbitrarily vertex decomposable unicyclic graphs with dominating cycle

Sylwia Cichacz, Irmina A. Zioło (2006)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (n₁,...,nₖ) of positive integers such that $\sum_{i = 1}^{k} n_{i} = n$ , there exists a partition (V₁,...,Vₖ) of vertex set of G such that for every i ∈ 1,...,k the set $V_{i}$ induces a connected subgraph of G on $n_{i}$ vertices. We consider arbitrarily vertex decomposable unicyclic graphs with dominating cycle. We also characterize all such graphs with at most four hanging vertices such that exactly two of them have a common neighbour. ...

On a family of cubic graphs containing the flower snarks

Jean-Luc Fouquet, Henri Thuillier, Jean-Marie Vanherpe (2010)

Discussiones Mathematicae Graph Theory

Similarity:

We consider cubic graphs formed with k ≥ 2 disjoint claws $C_{i} K_{1, 3}$ (0 ≤ i ≤ k-1) such that for every integer i modulo k the three vertices of degree 1 of $C_{i}$ are joined to the three vertices of degree 1 of $C_{i - 1}$ and joined to the three vertices of degree 1 of $C_{i + 1}$ . Denote by $t_{i}$ the vertex of degree 3 of $C_{i}$ and by T the set $t ₁, t ₂, . . ., t_{k - 1}$ . In such a way we construct three distinct graphs, namely FS(1,k), FS(2,k) and FS(3,k). The graph FS(j,k) (j ∈ 1,2,3) is the graph where the set of vertices $⋃_{i = 0}^{i = k - 1} V (C_{i}) ∖ T$ induce j cycles (note...

Cycle-pancyclism in bipartite tournaments II

Hortensia Galeana-Sánchez (2004)

Discussiones Mathematicae Graph Theory

Similarity:

Let T be a hamiltonian bipartite tournament with n vertices, γ a hamiltonian directed cycle of T, and k an even number. In this paper the following question is studied: What is the maximum intersection with γ of a directed cycle of length k contained in T[V(γ)]? It is proved that for an even k in the range (n+6)/2 ≤ k ≤ n-2, there exists a directed cycle $C_{h (k)}$ of length h(k), h(k) ∈ k,k-2 with $| A (C_{h (k)}) \cap A (γ) | \geq h (k) - 4$ and the result is best possible. In a previous paper a similar result for 4 ≤ k ≤ (n+4)/2 was...

Domination and independence subdivision numbers of graphs

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The domination subdivision number $s d_{γ} (G)$ of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of...

4-cycle properties for characterizing rectagraphs and hypercubes

Khadra Bouanane, Abdelhafid Berrachedi (2017)

Czechoslovak Mathematical Journal

Similarity:

A $(0, 2)$ -graph is a connected graph, where each pair of vertices has either 0 or 2 common neighbours. These graphs constitute a subclass of $(0, λ)$ -graphs introduced by Mulder in 1979. A rectagraph, well known in diagram geometry, is a triangle-free $(0, 2)$ -graph. $(0, 2)$ -graphs include hypercubes, folded cube graphs and some particular graphs such as icosahedral graph, Shrikhande graph, Klein graph, Gewirtz graph, etc. In this paper, we give some local properties of 4-cycles in $(0, λ)$ -graphs and more specifically...

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.

Displaying similar documents to “Pairs of forbidden class of subgraphs concerning K 1 , 3 and P₆ to have a cycle containing specified vertices”

Displaying similar documents to “Pairs of forbidden class of subgraphs concerning $K_{1, 3}$ and P₆ to have a cycle containing specified vertices”