Graphs with convex domination number close to their order

Joanna Cyman; Magdalena Lemańska; Joanna Raczek

Displaying similar documents to “Graphs with convex domination number close to their order”

The forcing convexity number of a graph

Gary Chartrand, Ping Zhang (2001)

Czechoslovak Mathematical Journal

Similarity:

For two vertices $u$ and $v$ of a connected graph $G$ , the set $I (u, v)$ consists of all those vertices lying on a $u$ – $v$ geodesic in $G$ . For a set $S$ of vertices of $G$ , the union of all sets $I (u, v)$ for $u, v \in S$ is denoted by $I (S)$ . A set $S$ is a convex set if $I (S) = S$ . The convexity number $c o n (G)$ of $G$ is the maximum cardinality of a proper convex set of $G$ . A convex set $S$ in $G$ with $| S | = c o n (G)$ is called a maximum convex set. A subset $T$ of a maximum convex set $S$ of a connected graph $G$ is called a forcing subset for $S$ if $S$ is the unique maximum...

$H$ -convex graphs

Gary Chartrand, Ping Zhang (2001)

Mathematica Bohemica

Similarity:

For two vertices $u$ and $v$ in a connected graph $G$ , the set $I (u, v)$ consists of all those vertices lying on a $u - v$ geodesic in $G$ . For a set $S$ of vertices of $G$ , the union of all sets $I (u, v)$ for $u, v \in S$ is denoted by $I (S)$ . A set $S$ is convex if $I (S) = S$ . The convexity number $c o n (G)$ is the maximum cardinality of a proper convex set in $G$ . A convex set $S$ is maximum if $| S | = c o n (G)$ . The cardinality of a maximum convex set in a graph $G$ is the convexity number of $G$ . For a nontrivial connected graph $H$ , a connected graph $G$ is an $H$ -convex graph...

Convex universal fixers

Magdalena Lemańska, Rita Zuazua (2012)

Discussiones Mathematicae Graph Theory

Similarity:

In [1] Burger and Mynhardt introduced the idea of universal fixers. Let G = (V, E) be a graph with n vertices and G’ a copy of G. For a bijective function π: V(G) → V(G’), define the prism πG of G as follows: V(πG) = V(G) ∪ V(G’) and $E (π G) = E (G) \cup E (G^{'}) \cup M_{π}$ , where $M_{π} = u π (u) | u \in V (G)$ . Let γ(G) be the domination number of G. If γ(πG) = γ(G) for any bijective function π, then G is called a universal fixer. In [9] it is conjectured that the only universal fixers are the edgeless graphs K̅ₙ. In this work we generalize the concept...

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

On some results about convex functions of order $α$

M. Obradović, S. Owa (1986)

Matematički Vesnik

Similarity:

The Young inequality and the Δ₂-condition

Philippe Laurençot (2002)

Colloquium Mathematicae

Similarity:

If φ: [0,∞) → [0,∞) is a convex function with φ(0) = 0 and conjugate function φ*, the inequality $x y \leq ε φ (x) + C_{ε} φ * (y)$ is shown to hold true for every ε ∈ (0,∞) if and only if φ* satisfies the Δ₂-condition.

Convex integration with constraints and applications to phase transitions and partial differential equations

Stefan Müller, Vladimír Šverák (1999)

Journal of the European Mathematical Society

Similarity:

We study solutions of first order partial differential relations $D u \in K$ , where $u : Ω \subset ℝ^{n} \to ℝ^{m}$ is a Lipschitz map and $K$ is a bounded set in $m \times n$ matrices, and extend Gromov’s theory of convex integration in two ways. First, we allow for additional constraints on the minors of $D u$ and second we replace Gromov’s $P$ −convex hull by the (functional) rank-one convex hull. The latter can be much larger than the former and this has important consequences for the existence of ‘wild’ solutions to elliptic systems. Our...

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

The hull number of strong product graphs

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

Discussiones Mathematicae Graph Theory

Similarity:

For a connected graph G with at least two vertices and S a subset of vertices, the convex hull ${[S]}_{G}$ is the smallest convex set containing S. The hull number h(G) is the minimum cardinality among the subsets S of V(G) with ${[S]}_{G} = V (G)$ . Upper bound for the hull number of strong product G ⊠ H of two graphs G and H is obtainted. Improved upper bounds are obtained for some class of strong product graphs. Exact values for the hull number of some special classes of strong product graphs are obtained. Graphs...

The geodetic number of strong product graphs

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

Discussiones Mathematicae Graph Theory

Similarity:

For two vertices u and v of a connected graph G, the set $I_{G} [u, v]$ consists of all those vertices lying on u-v geodesics in G. Given a set S of vertices of G, the union of all sets $I_{G} [u, v]$ for u,v ∈ S is denoted by $I_{G} [S]$ . A set S ⊆ V(G) is a geodetic set if $I_{G} [S] = V (G)$ and the minimum cardinality of a geodetic set is its geodetic number g(G) of G. Bounds for the geodetic number of strong product graphs are obtainted and for several classes improved bounds and exact values are obtained.

Generalized characterization of the convex envelope of a function

Fethi Kadhi (2002)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

We investigate the minima of functionals of the form $\int_{[a, b]} g (\dot{u} (s)) d s$ where $g$ is strictly convex. The admissible functions $u : [a, b] \to ℝ$ are not necessarily convex and satisfy $u \leq f$ on $[a, b]$ , $u (a) = f (a)$ , $u (b) = f (b)$ , $f$ is a fixed function on $[a, b]$ . We show that the minimum is attained by $\bar{f}$ , the convex envelope of $f$ .

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.

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