Order of the smallest counterexample to Gallai's conjecture

Fuyuan Chen

Displaying similar documents to “Order of the smallest counterexample to Gallai's conjecture”

On a problem concerning $k$ -subdomination numbers of graphs

Bohdan Zelinka (2003)

Czechoslovak Mathematical Journal

Similarity:

One of numerical invariants concerning domination in graphs is the $k$ -subdomination number $γ_{k S}^{- 11} (G)$ of a graph $G$ . A conjecture concerning it was expressed by J. H. Hattingh, namely that for any connected graph $G$ with $n$ vertices and any $k$ with $\frac{1}{2} n < k ≦ n$ the inequality $γ_{k S}^{- 11} (G) ≦ 2 k - n$ holds. This paper presents a simple counterexample which disproves this conjecture. This counterexample is the graph of the three-dimensional cube and $k = 5$ .

Nonempty intersection of longest paths in a graph with a small matching number

Fuyuan Chen (2015)

Czechoslovak Mathematical Journal

Similarity:

A maximum matching of a graph $G$ is a matching of $G$ with the largest number of edges. The matching number of a graph $G$ , denoted by $α^{'} (G)$ , is the number of edges in a maximum matching of $G$ . In 1966, Gallai conjectured that all the longest paths of a connected graph have a common vertex. Although this conjecture has been disproved, finding some nice classes of graphs that support this conjecture is still very meaningful and interesting. In this short note, we prove that Gallai’s conjecture...

A remark on the (2,2)-domination number

Torsten Korneffel, Dirk Meierling, Lutz Volkmann (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A subset D of the vertex set of a graph G is a (k,p)-dominating set if every vertex v ∈ V(G)∖D is within distance k to at least p vertices in D. The parameter $γ_{k, p} (G)$ denotes the minimum cardinality of a (k,p)-dominating set of G. In 1994, Bean, Henning and Swart posed the conjecture that $γ_{k, p} (G) \leq (p / (p + k)) n (G)$ for any graph G with δₖ(G) ≥ k+p-1, where the latter means that every vertex is within distance k to at least k+p-1 vertices other than itself. In 2005, Fischermann and Volkmann confirmed this conjecture...

On the generalized vanishing conjecture

Zhenzhen Feng, Xiaosong Sun (2019)

Czechoslovak Mathematical Journal

Similarity:

We show that the GVC (generalized vanishing conjecture) holds for the differential operator $Λ = (\partial_{x} - Φ (\partial_{y})) \partial_{y}$ and all polynomials $P (x, y)$ , where $Φ (t)$ is any polynomial over the base field. The GVC arose from the study of the Jacobian conjecture.

Domination Subdivision Numbers

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi, David P. Jacobs, James Knisely, Lucas C. van der Merwe (2001)

Discussiones Mathematicae Graph Theory

Similarity:

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number $s d_{γ} (G)$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that $1 \leq s d_{γ} (G) \leq 3$ for any graph G. We give a counterexample to this conjecture. On the other hand,...

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

A note on periodicity of the 2-distance operator

Bohdan Zelinka (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The paper solves one problem by E. Prisner concerning the 2-distance operator T₂. This is an operator on the class $C_{f}$ of all finite undirected graphs. If G is a graph from $C_{f}$ , then T₂(G) is the graph with the same vertex set as G in which two vertices are adjacent if and only if their distance in G is 2. E. Prisner asks whether the periodicity ≥ 3 is possible for T₂. In this paper an affirmative answer is given. A result concerning the periodicity 2 is added.

On the Brocard-Ramanujan problem and generalizations

Andrzej Dąbrowski (2012)

Colloquium Mathematicae

Similarity:

Let $p_{i}$ denote the ith prime. We conjecture that there are precisely 28 solutions to the equation $n ² - 1 = p ₁^{α ₁} \dots p_{k}^{α_{k}}$ in positive integers n and α₁,..., $α_{k}$ . This conjecture implies an explicit description of the set of solutions to the Brocard-Ramanujan equation. We also propose another variant of the Brocard-Ramanujan problem: describe the set of solutions in non-negative integers of the equation n! + A = x₁²+x₂²+x₃² (A fixed).

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

On a number theoretic conjecture on positive integral points in a 5-dimensional tetrahedron and a sharp estimate of the Dickman–De Bruijn function

Ke-Pao Lin, Xue Luo, Stephen S.-T. Yau, Huaiqing Zuo (2014)

Journal of the European Mathematical Society

Similarity:

It is well known that getting the estimate of integral points in right-angled simplices is equivalent to getting the estimate of Dickman-De Bruijn function $ψ (x, y)$ which is the number of positive integers $\leq x$ and free of prime factors $> y$ . Motivating from the Yau Geometry Conjecture, the third author formulated the Number Theoretic Conjecture which gives a sharp polynomial upper estimate that counts the number of positive integral points in n-dimensional ( $n \geq 3$ ) real right-angled simplices. In this...