The Degree-Diameter Problem for Outerplanar Graphs

Peter Dankelmann; Elizabeth Jonck; Tomáš Vetrík

Displaying similar documents to “The Degree-Diameter Problem for Outerplanar Graphs”

Maximal k-independent sets in graphs

Mostafa Blidia, Mustapha Chellali, Odile Favaron, Nacéra Meddah (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A subset of vertices of a graph G is k-independent if it induces in G a subgraph of maximum degree less than k. The minimum and maximum cardinalities of a maximal k-independent set are respectively denoted iₖ(G) and βₖ(G). We give some relations between βₖ(G) and $β_{j} (G)$ and between iₖ(G) and $i_{j} (G)$ for j ≠ k. We study two families of extremal graphs for the inequality i₂(G) ≤ i(G) + β(G). Finally we give an upper bound on i₂(G) and a lower bound when G is a cactus.

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.

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.

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.

On the minus domination number of graphs

Hailong Liu, Liang Sun (2004)

Czechoslovak Mathematical Journal

Similarity:

Let $G = (V, E)$ be a simple graph. A $3$ -valued function $f V (G) \to {- 1, 0, 1}$ is said to be a minus dominating function if for every vertex $v \in V$ , $f (N [v]) = \sum_{u \in N [v]} f (u) \geq 1$ , where $N [v]$ is the closed neighborhood of $v$ . The weight of a minus dominating function $f$ on $G$ is $f (V) = \sum_{v \in V} f (v)$ . The minus domination number of a graph $G$ , denoted by $γ^{-} (G)$ , equals the minimum weight of a minus dominating function on $G$ . In this paper, the following two results are obtained. (1) If $G$ is a bipartite graph of order $n$ , then $γ^{-} (G) \geq 4 (\sqrt{n + 1} - 1) - n .$ (2) For any negative integer $k$ and any positive integer...

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

On the total k-domination number of graphs

Adel P. Kazemi (2012)

Discussiones Mathematicae Graph Theory

Similarity:

Let k be a positive integer and let G = (V,E) be a simple graph. The k-tuple domination number $γ_{\times k} (G)$ of G is the minimum cardinality of a k-tuple dominating set S, a set that for every vertex v ∈ V, $| N_{G} [v] \cap S | \geq k$ . Also the total k-domination number $γ_{\times k, t} (G)$ of G is the minimum cardinality of a total k -dominating set S, a set that for every vertex v ∈ V, $| N_{G} (v) \cap S | \geq k$ . The k-transversal number τₖ(H) of a hypergraph H is the minimum size of a subset S ⊆ V(H) such that |S ∩e | ≥ k for every edge e ∈ E(H). We know that for...

Roman bondage in graphs

Nader Jafari Rad, Lutz Volkmann (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A Roman dominating function on a graph G is a function f:V(G) → 0,1,2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of a Roman dominating function is the value $f (V (G)) = \sum_{u \in V (G)} f (u)$ . The Roman domination number, $γ_{R} (G)$ , of G is the minimum weight of a Roman dominating function on G. In this paper, we define the Roman bondage $b_{R} (G)$ of a graph G with maximum degree at least two to be the minimum cardinality of all sets E’ ⊆ E(G)...

Two variants of the size Ramsey number

Andrzej Kurek, Andrzej Ruciński (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Given a graph H and an integer r ≥ 2, let G → (H,r) denote the Ramsey property of a graph G, that is, every r-coloring of the edges of G results in a monochromatic copy of H. Further, let $m (G) = m a x_{F \subseteq G} | E (F) | / | V (F) |$ and define the Ramsey density $m_{i n f} (H, r)$ as the infimum of m(G) over all graphs G such that G → (H,r). In the first part of this paper we show that when H is a complete graph Kₖ on k vertices, then $m_{i n f} (H, r) = (R - 1) / 2$ , where R = R(k;r) is the classical Ramsey number. As a corollary we derive a new proof of the result credited...

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

Extremal properties of distance-based graph invariants for $k$ -trees

Minjie Zhang, Shuchao Li (2018)

Mathematica Bohemica

Similarity:

Sharp bounds on some distance-based graph invariants of $n$ -vertex $k$ -trees are established in a unified approach, which may be viewed as the weighted Wiener index or weighted Harary index. The main techniques used in this paper are graph transformations and mathematical induction. Our results demonstrate that among $k$ -trees with $n$ vertices the extremal graphs with the maximal and the second maximal reciprocal sum-degree distance are coincident with graphs having the maximal and the second...

On characterization of uniquely 3-list colorable complete multipartite graphs

Yancai Zhao, Erfang Shan (2010)

Discussiones Mathematicae Graph Theory

Similarity:

For each vertex v of a graph G, if there exists a list of k colors, L(v), such that there is a unique proper coloring for G from this collection of lists, then G is called a uniquely k-list colorable graph. Ghebleh and Mahmoodian characterized uniquely 3-list colorable complete multipartite graphs except for nine graphs: $K_{2, 2, r}$ r ∈ 4,5,6,7,8, $K_{2, 3, 4}$ , $K_{1 * 4, 4}$ , $K_{1 * 4, 5}$ , $K_{1 * 5, 4}$ . Also, they conjectured that the nine graphs are not U3LC graphs. After that, except for $K_{2, 2, r}$ r ∈ 4,5,6,7,8, the others have been proved not...