### Connected graphs containing a given connected graph as a unique greatest common subgraph.

Skip to main content (access key 's'),
Skip to navigation (access key 'n'),
Accessibility information (access key '0')

Back to Simple Search
# Advanced Search

We show that for every integer k ≥ 2 and every k graphs G₁,G₂,...,Gₖ, there exists a hull graph with k hull vertices v₁,v₂,...,vₖ such that link $L\left({v}_{i}\right)={G}_{i}$ for 1 ≤ i ≤ k. Moreover, every pair a, b of integers with 2 ≤ a ≤ b is realizable as the hull number and geodetic number (or upper geodetic number) of a hull graph. We also show that every pair a,b of integers with a ≥ 2 and b ≥ 0 is realizable as the hull number and forcing geodetic number of a hull graph.

For two vertices u and v of a graph G, the set I(u, v) consists of all vertices lying on some u-v geodesic in G. If S is a set of vertices of G, then I(S) is the union of all sets I(u,v) for u, v ∈ S. A set S is a geodetic set if I(S) = V(G). A minimum geodetic set is a geodetic set of minimum cardinality and this cardinality is the geodetic number g(G). A subset T of a minimum geodetic set S is called a forcing subset for S if S is the unique minimum geodetic set containing T. The forcing geodetic...

For two vertices $u$ and $v$ of a graph $G$, the closed interval $I[u,v]$ consists of $u$, $v$, and all vertices lying in some $u\text{--}v$ geodesic of $G$, while for $S\subseteq V\left(G\right)$, the set $I\left[S\right]$ is the union of all sets $I[u,v]$ for $u,v\in S$. A set $S$ of vertices of $G$ for which $I\left[S\right]=V\left(G\right)$ is a geodetic set for $G$, and the minimum cardinality of a geodetic set is the geodetic number $g\left(G\right)$. A vertex $v$ in $G$ is an extreme vertex if the subgraph induced by its neighborhood is complete. The number of extreme vertices in $G$ is its extreme order $\mathrm{e}x\left(G\right)$. A graph $G$ is an extreme geodesic...

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\left(S\right)$. A set $S$ is a convex set if $I\left(S\right)=S$. The convexity number $\mathrm{c}on\left(G\right)$ of $G$ is the maximum cardinality of a proper convex set of $G$. A convex set $S$ in $G$ with $\left|S\right|=\mathrm{c}on\left(G\right)$ 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 convex set...

For an ordered set $W=\{{w}_{1},{w}_{2},\cdots ,{w}_{k}\}$ of vertices and a vertex $v$ in a connected graph $G$, the (metric) representation of $v$ with respect to $W$ is the $k$-vector $r\left(v\right|W)$ = ($d(v,{w}_{1}),d(v,{w}_{2}),\cdots ,d(v,{w}_{k})$), where $d(x,y)$ represents the distance between the vertices $x$ and $y$. The set $W$ is a resolving set for $G$ if distinct vertices of $G$ have distinct representations. A resolving set of minimum cardinality is a basis for $G$ and the number of vertices in a basis is its (metric) dimension $dim\left(G\right)$. For a basis $W$ of $G$, a subset $S$ of $W$ is called a forcing subset of $W$ if $W$ is...

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\left(S\right)$. A set $S$ is convex if $I\left(S\right)=S$. The convexity number $\mathrm{c}on\left(G\right)$ is the maximum cardinality of a proper convex set in $G$. A convex set $S$ is maximum if $\left|S\right|=\mathrm{c}on\left(G\right)$. 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 if $G$ contains...

For two vertices u and v of a graph G, the closed interval I[u,v] consists of u, v, and all vertices lying in some u-v geodesic in G. If S is a set of vertices of G, then I[S] is the union of all sets I[u,v] for u, v ∈ S. If I[S] = V(G), then S is a geodetic set for G. The geodetic number g(G) is the minimum cardinality of a geodetic set. A set S of vertices in a graph G is uniform if the distance between every two distinct vertices of S is the same fixed number. A geodetic set is essential if for...

For a spanning tree T in a nontrivial connected graph G and for vertices u and v in G, there exists a unique u-v path u = u₀, u₁, u₂,..., uₖ = v in T. A u-v T-path in G is a u- v path u = v₀, v₁,...,vₗ = v in G that is a subsequence of the sequence u = u₀, u₁, u₂,..., uₖ = v. A u-v T-path of minimum length is a u-v T-geodesic in G. The T-distance ${d}_{G|T}(u,v)$ from u to v in G is the length of a u-v T-geodesic. Let geo(G) and geo(G|T) be the set of geodesics and the set of T-geodesics respectively in G. Necessary...

For a connected graph G of diameter d and an integer k with 1 ≤ k ≤ d, a radio k-coloring of G is an assignment c of colors (positive integers) to the vertices of G such that d(u,v) + |c(u)- c(v)| ≥ 1 + k for every two distinct vertices u and v of G, where d(u,v) is the distance between u and v. The value rcₖ(c) of a radio k-coloring c of G is the maximum color assigned to a vertex of G. The radio k-chromatic number rcₖ(G) of G is the minimum value of rcₖ(c) taken over all radio k-colorings c of...

For an r-regular graph G, let c : E(G) → [k] = 1, 2, . . . , k, k ≥ 3, be an edge coloring of G, where every vertex of G is incident with at least one edge of each color. For a vertex v of G, the multiset-color cm(v) of v is defined as the ordered k-tuple (a1, a2, . . . , ak) or a1a2 … ak, where ai (1 ≤ i ≤ k) is the number of edges in G colored i that are incident with v. The edge coloring c is called k-kaleidoscopic if cm(u) ≠ cm(v) for every two distinct vertices u and v of G. A regular graph...

**Page 1**
Next