Light classes of generalized stars in polyhedral maps on surfaces

Stanislav Jendrol'; Heinz-Jürgen Voss

Displaying similar documents to “Light classes of generalized stars in polyhedral maps on surfaces”

Light paths with an odd number of vertices in polyhedral maps

Stanislav Jendroľ, Heinz-Jürgen Voss (2000)

Czechoslovak Mathematical Journal

Similarity:

Let $P_{k}$ be a path on $k$ vertices. In an earlier paper we have proved that each polyhedral map $G$ on any compact $2$ -manifold $𝕄$ with Euler characteristic $χ (𝕄) \leq 0$ contains a path $P_{k}$ such that each vertex of this path has, in $G$ , degree $\leq k ⌊\frac{5 + \sqrt{49 - 24 χ (𝕄)}}{2}⌋$ . Moreover, this bound is attained for $k = 1$ or $k \geq 2$ , $k$ even. In this paper we prove that for each odd $k \geq \frac{4}{3} ⌊\frac{5 + \sqrt{49 - 24 χ (𝕄)}}{2}⌋ + 1$ , this bound is the best possible on infinitely many compact $2$ -manifolds, but on infinitely many other compact $2$ -manifolds the upper bound can be lowered to $⌊(k - \frac{1}{3}) \frac{5 + \sqrt{49 - 24 χ (𝕄)}}{2}⌋$ .

Paths of low weight in planar graphs

Igor Fabrici, Jochen Harant, Stanislav Jendrol' (2008)

Discussiones Mathematicae Graph Theory

Similarity:

The existence of paths of low degree sum of their vertices in planar graphs is investigated. The main results of the paper are: 1. Every 3-connected simple planar graph G that contains a k-path, a path on k vertices, also contains a k-path P such that for its weight (the sum of degrees of its vertices) in G it holds $w_{G} (P) : = \sum_{u \in V (P)} d e g_{G} (u) \leq (3 / 2) k ² + (k)$ 2. Every plane triangulation T that contains a k-path also contains a k-path P such that for its weight in T it holds $w_{T} (P) : = \sum_{u \in V (P)} d e g_{T} (u) \leq k ² + 13 k$ 3. Let G be a 3-connected simple planar graph of...

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

Graphs with large double domination numbers

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)$ . If G ≠ C₅ is a connected graph of order n with minimum degree at least 2, then we show that $γ_{\times 2} (G) \leq 3 n / 4$ and we characterize those graphs achieving equality.

Double domination critical and stable graphs upon vertex removal

Soufiane Khelifi, Mustapha Chellali (2012)

Discussiones Mathematicae Graph Theory

Similarity:

In a graph a vertex is said to dominate itself and all its neighbors. A double dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. The double domination number of G, denoted $γ_{\times 2} (G)$ , is the minimum cardinality among all double dominating sets of G. We consider the effects of vertex removal on the double domination number of a graph. A graph G is $γ_{\times 2}$ -vertex critical graph ( $γ_{\times 2}$ -vertex stable graph, respectively) if the removal of any vertex different...

On $k$ -pairable graphs from trees

Zhongyuan Che (2007)

Czechoslovak Mathematical Journal

Similarity:

The concept of the $k$ -pairable graphs was introduced by Zhibo Chen (On $k$ -pairable graphs, Discrete Mathematics 287 (2004), 11–15) as an extension of hypercubes and graphs with an antipodal isomorphism. In the same paper, Chen also introduced a new graph parameter $p (G)$ , called the pair length of a graph $G$ , as the maximum $k$ such that $G$ is $k$ -pairable and $p (G) = 0$ if $G$ is not $k$ -pairable for any positive integer $k$ . In this paper, we answer the two open questions raised by Chen in the case that the graphs...

Solution to the problem of Kubesa

Mariusz Meszka (2008)

Discussiones Mathematicae Graph Theory

Similarity:

An infinite family of T-factorizations of complete graphs $K_{2 n}$ , where 2n = 56k and k is a positive integer, in which the set of vertices of T can be split into two subsets of the same cardinality such that degree sums of vertices in both subsets are not equal, is presented. The existence of such T-factorizations provides a negative answer to the problem posed by Kubesa.

Weak roman domination in graphs

P. Roushini Leely Pushpam, T.N.M. Malini Mai (2011)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph and f be a function f:V → 0,1,2. A vertex u with f(u) = 0 is said to be undefended with respect to f, if it is not adjacent to a vertex with positive weight. The function f is a weak Roman dominating function (WRDF) if each vertex u with f(u) = 0 is adjacent to a vertex v with f(v) > 0 such that the function f’: V → 0,1,2 defined by f’(u) = 1, f’(v) = f(v)-1 and f’(w) = f(w) if w ∈ V-u,v, has no undefended vertex. The weight of f is $w (f) = \sum_{v \in V} f (v)$ . The weak Roman domination...

Graceful signed graphs

Mukti Acharya, Tarkeshwar Singh (2004)

Czechoslovak Mathematical Journal

Similarity:

A $(p, q)$ -sigraph $S$ is an ordered pair $(G, s)$ where $G = (V, E)$ is a $(p, q)$ -graph and $s$ is a function which assigns to each edge of $G$ a positive or a negative sign. Let the sets $E^{+}$ and $E^{-}$ consist of $m$ positive and $n$ negative edges of $G$ , respectively, where $m + n = q$ . Given positive integers $k$ and $d$ , $S$ is said to be $(k, d)$ -graceful if the vertices of $G$ can be labeled with distinct integers from the set ${0, 1, \dots, k + (q - 1) d}$ such that when each edge $u v$ of $G$ is assigned the product of its sign and the absolute difference of the integers assigned to...

Arbitrarily vertex decomposable caterpillars with four or five leaves

Sylwia Cichacz, Agnieszka Görlich, Antoni Marczyk, Jakub Przybyło, Mariusz Woźniak (2006)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (a₁,...,aₖ) of positive integers such that a₁+...+aₖ = n there exists a partition (V₁,...,Vₖ) of the vertex set of G such that for each i ∈ 1,...,k, $V_{i}$ induces a connected subgraph of G on $a_{i}$ vertices. D. Barth and H. Fournier showed that if a tree T is arbitrarily vertex decomposable, then T has maximum degree at most 4. In this paper we give a complete characterization of arbitrarily vertex decomposable...

Coalescing Fiedler and core vertices

Didar A. Ali, John Baptist Gauci, Irene Sciriha, Khidir R. Sharaf (2016)

Czechoslovak Mathematical Journal

Similarity:

The nullity of a graph $G$ is the multiplicity of zero as an eigenvalue in the spectrum of its adjacency matrix. From the interlacing theorem, derived from Cauchy’s inequalities for matrices, a vertex of a graph can be a core vertex if, on deleting the vertex, the nullity decreases, or a Fiedler vertex, otherwise. We adopt a graph theoretical approach to determine conditions required for the identification of a pair of prescribed types of root vertices of two graphs to form a cut-vertex...

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 in partitioned graphs

Zsolt Tuza, Preben Dahl Vestergaard (2002)

Discussiones Mathematicae Graph Theory

Similarity:

Let V₁, V₂ be a partition of the vertex set in a graph G, and let $γ_{i}$ denote the least number of vertices needed in G to dominate $V_{i}$ . We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest...

Bounds On The Disjunctive Total Domination Number Of A Tree

Michael A. Henning, Viroshan Naicker (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, γt(G). A set S of vertices in G is a disjunctive total dominating set of G if every vertex is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it. The disjunctive total domination number, [...] γtd(G) $γ_{t}^{d} (G)$ , is the minimum cardinality of such a set. We observe that [...] γtd(G)≤γt(G)...