On-line ranking number for cycles and paths

Erik Bruoth; Mirko Horňák

Displaying similar documents to “On-line ranking number for cycles and paths”

Stronger bounds for generalized degrees and Menger path systems

R.J. Faudree, Zs. Tuza (1995)

Discussiones Mathematicae Graph Theory

Similarity:

For positive integers d and m, let $P_{d, m} (G)$ denote the property that between each pair of vertices of the graph G, there are m internally vertex disjoint paths of length at most d. For a positive integer t a graph G satisfies the minimum generalized degree condition δₜ(G) ≥ s if the cardinality of the union of the neighborhoods of each set of t vertices of G is at least s. Generalized degree conditions that ensure that $P_{d, m} (G)$ is satisfied have been investigated. In particular, it has been shown,...

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

The vertex detour hull number of a graph

A.P. Santhakumaran, S.V. Ullas Chandran (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For vertices x and y in a connected graph G, the detour distance D(x,y) is the length of a longest x - y path in G. An x - y path of length D(x,y) is an x - y detour. The closed detour interval ID[x,y] consists of x,y, and all vertices lying on some x -y detour of G; while for S ⊆ V(G), $I_{D} [S] = ⋃_{x, y \in S} I_{D} [x, y]$ . A set S of vertices is a detour convex set if $I_{D} [S] = S$ . The detour convex hull ${[S]}_{D}$ is the smallest detour convex set containing S. The detour hull number dh(G) is the minimum cardinality among subsets S of...

Sum labellings of cycle hypergraphs

Hanns-Martin Teichert (2000)

Discussiones Mathematicae Graph Theory

Similarity:

A hypergraph is a sum hypergraph iff there are a finite S ⊆ IN⁺ and d̲, [d̅] ∈ IN⁺ with 1 < d̲ ≤ [d̅] such that is isomorphic to the hypergraph $_{d ̲, [d ̅]} (S) = (V,)$ where V = S and $= e \subseteq S : d ̲ \leq | e | \leq [d ̅] \land \sum_{v \in e} v \in S$ . For an arbitrary hypergraph the sum number σ = σ() is defined to be the minimum number of isolated vertices $y ₁, . . ., y_{σ} \notin V$ such that $\cup y ₁, . . ., y_{σ}$ is a sum hypergraph. Generalizing the graph Cₙ we obtain d-uniform hypergraphs where any d consecutive vertices of Cₙ form an edge. We determine sum numbers and investigate properties of sum labellings...

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

Full domination in graphs

Robert C. Brigham, Gary Chartrand, Ronald D. Dutton, Ping Zhang (2001)

Discussiones Mathematicae Graph Theory

Similarity:

For each vertex v in a graph G, let there be associated a subgraph $H_{v}$ of G. The vertex v is said to dominate $H_{v}$ as well as dominate each vertex and edge of $H_{v}$ . A set S of vertices of G is called a full dominating set if every vertex of G is dominated by some vertex of S, as is every edge of G. The minimum cardinality of a full dominating set of G is its full domination number $γ_{F H} (G)$ . A full dominating set of G of cardinality $γ_{F H} (G)$ is called a $γ_{F H}$ -set of G. We study three types of full domination in...

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

Fires on trees

Jean Bertoin (2012)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We consider random dynamics on the edges of a uniform Cayley tree with $n$ vertices, in which edges are either flammable, fireproof, or burnt. Every flammable edge is replaced by a fireproof edge at unit rate, while fires start at smaller rate $n^{- α}$ on each flammable edge, then propagate through the neighboring flammable edges and are only stopped at fireproof edges. A vertex is called fireproof when all its adjacent edges are fireproof. We show that as $n \to \infty$ , the terminal density of fireproof...

On the heterochromatic number of circulant digraphs

Hortensia Galeana-Sánchez, Víctor Neumann-Lara (2004)

Discussiones Mathematicae Graph Theory

Similarity:

The heterochromatic number hc(D) of a digraph D, is the minimum integer k such that for every partition of V(D) into k classes, there is a cyclic triangle whose three vertices belong to different classes. For any two integers s and n with 1 ≤ s ≤ n, let $D_{n, s}$ be the oriented graph such that $V (D_{n, s})$ is the set of integers mod 2n+1 and $A (D_{n, s}) = (i, j) : j - i \in 1, 2, . . ., n ∖ s . .$ In this paper we prove that $h c (D_{n, s}) \leq 5$ for n ≥ 7. The bound is tight since equality holds when s ∈ n,[(2n+1)/3].

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

2-factors in claw-free graphs with locally disconnected vertices

Mingqiang An, Liming Xiong, Runli Tian (2015)

Czechoslovak Mathematical Journal

Similarity:

An edge of $G$ is singular if it does not lie on any triangle of $G$ ; otherwise, it is non-singular. A vertex $u$ of a graph $G$ is called locally connected if the induced subgraph $G [N (u)]$ by its neighborhood is connected; otherwise, it is called locally disconnected. In this paper, we prove that if a connected claw-free graph $G$ of order at least three satisfies the following two conditions: (i) for each locally disconnected vertex $v$ of degree at least $3$ in $G,$ there is a nonnegative integer $s$ such...

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})$ .

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.

On locating-domination in graphs

Mustapha Chellali, Malika Mimouni, Peter J. Slater (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A set D of vertices in a graph G = (V,E) is a locating-dominating set (LDS) if for every two vertices u,v of V-D the sets N(u)∩ D and N(v)∩ D are non-empty and different. The locating-domination number $γ_{L} (G)$ is the minimum cardinality of a LDS of G, and the upper locating-domination number, $Γ_{L} (G)$ is the maximum cardinality of a minimal LDS of G. We present different bounds on $Γ_{L} (G)$ and $γ_{L} (G)$ .

On double domination in graphs

Jochen Harant, Michael A. Henning (2005)

Discussiones Mathematicae Graph Theory

Similarity:

In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number $γ_{\times 2} (G)$ . A function f(p) is defined, and it is shown that $γ_{\times 2} (G) = m i n f (p)$ , where the minimum is taken over the n-dimensional cube $C ⁿ = p = (p ₁, . . ., p ₙ) | p_{i} \in I R, 0 \leq p_{i} \leq 1, i = 1, . . ., n$ . Using this result, it is then shown that if G has order n with minimum degree δ and average degree d, then $γ_{\times 2} (G) \leq ((l n (1 + d) + l n δ + 1) / δ) n$ .

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