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

Wiener index of graphs with fixed number of pendant or cut-vertices

Dinesh Pandey, Kamal Lochan Patra (2022)

Czechoslovak Mathematical Journal

Similarity:

The Wiener index of a connected graph is defined as the sum of the distances between all unordered pairs of its vertices. We characterize the graphs which extremize the Wiener index among all graphs on $n$ vertices with $k$ pendant vertices. We also characterize the graph which minimizes the Wiener index over the graphs on $n$ vertices with $s$ cut-vertices.

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