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

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.

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