For a nontrivial connected graph $F$, the $F$-degree of a vertex $v$ in a graph $G$ is the number of copies of $F$ in $G$ containing $v$. A graph $G$ is $F$-continuous (or $F$-degree continuous) if the $F$-degrees of every two adjacent vertices of $G$ differ by at most 1. All $P_3$-continuous graphs are determined. It is observed that if $G$ is a nontrivial connected graph that is $F$-continuous for all nontrivial connected graphs $F$, then either $G$ is regular or $G$ is a path. In the case of a 2-connected graph $F$, however, there always exists a regular graph that is not $F$-continuous. It is also shown that for every graph $H$ and every 2-connected graph $F$, there exists an $F$-continuous graph $G$ containing $H$ as an induced subgraph.
For an ordered set $W=\lbrace w_1, w_2, \dots , w_k\rbrace $ of vertices and a vertex $v$ in a connected graph $G$, the representation of $v$ with respect to $W$ is the $k$-vector $r(v|W)$ = ($d(v, w_1)$, $d(v, w_2),\dots ,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 with respect to $W$. A resolving set for $G$ containing a minimum number of vertices is a basis for $G$. The dimension $\dim (G)$ is the number of vertices in a basis for $G$. A resolving set $W$ of $G$ is connected if the subgraph $<W>$ induced by $W$ is a nontrivial connected subgraph of $G$. The minimum cardinality of a connected resolving set in a graph $G$ is its connected resolving number $\mathop {\mathrm cr}(G)$. Thus $1 \le \dim (G) \le \mathop {\mathrm cr}(G) \le n-1$ for every connected graph $G$ of order $n \ge 3$. The connected resolving numbers of some well-known graphs are determined. It is shown that if $G$ is a connected graph of order $n \ge 3$, then $\mathop {\mathrm cr}(G) = n-1$ if and only if $G = K_n$ or $G = K_{1, n-1}$. It is also shown that for positive integers $a$, $b$ with $a \le b$, there exists a connected graph $G$ with $\dim (G) = a$ and $\mathop {\mathrm cr}(G) = b$ if and only if $(a, b) \notin \lbrace
(1, k)\: k = 1\hspace{5.0pt}\text{or}\hspace{5.0pt}k \ge 3\rbrace $. Several other realization results are present. The connected resolving numbers of the Cartesian products $G \times K_2$ for connected graphs $G$ are studied.
For an ordered k-decomposition D = {G1, G2, . . . , Gk} of a connected graph G and an edge e of G, the D-code of e is the k-tuple cD(e) = (d(e, G1), d(e, G2), . . . , d(e, Gk)), where d(e, Gi) is the distance from e to Gi . A decomposition D is resolving if every two distinct edges of G have distinct D-codes. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dimd(G). A resolving decomposition D of G is connected if each Gi is connected for 1 ≤ i ≤ k. The minimum k for which G has a connected resolving k-decomposition is its connected decomposition number cd(G). Thus 2 ≤ dimd(G) ≤ cd(G) ≤ m for every connected graph G of size m ≥ 2. All nontrivial connected graphs with connected decomposition number 2 or m are characterized. We provide bounds for the connected decomposition number of a connected graph in terms of its size, diameter, girth, and other parameters. A formula for the connected decomposition number of a nonpath tree is established. It is shown that, for every pair a, b of integers with 3 ≤ a ≤ b, there exists a connected graph G with dimd(G) = a and cd(G) = b.
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(G)$, the set $I[S]$ is the union of all sets $I[u, v]$ for $u, v \in S$. A set $S$ of vertices of $G$ for which $I[S]=V(G)$ is a geodetic set for $G$, and the minimum cardinality of a geodetic set is the geodetic number $g(G)$. 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 $\mathop {\mathrm ex}(G)$. A graph $G$ is an extreme geodesic graph if $g(G) = \mathop {\mathrm ex}(G)$, that is, if every vertex lies on a $u\text{--}v$ geodesic for some pair $u$, $ v$ of extreme vertices. It is shown that every pair $a$, $ b$ of integers with $0 \le a \le b$ is realizable as the extreme order and geodetic number, respectively, of some graph. For positive integers $r, d,$ and $k \ge 2$, it is shown that there exists an extreme geodesic graph $G$ of radius $r$, diameter $d$, and geodetic number $k$. Also, for integers $n$, $ d, $ and $k$ with $2 \le d < n$, $2 \le k < n$, and $n -d - k +1 \ge 0$, there exists a connected extreme geodesic graph $G$ of order $n$, diameter $d$, and geodetic number $k$. We show that every graph of order $n$ with geodetic number $n-1$ is an extreme geodesic graph. On the other hand, for every pair $k$, $ n$ of integers with
$2 \le k \le n-2$, there exists a connected graph of order $n$ with geodetic number $k$ that is not an extreme geodesic graph.
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 ∈ S is denoted by I(S). A set S is convex if I(S) = S. The convexity number con(G) is the maximum cardinality of a proper convex set in G. A convex set S is maximum if |S| = con(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 if G contains a maximum convex set S whose induced subgraph is S = H. It is shown that for every positive integer k, there exist k pairwise nonisomorphic graphs H1, H2,...,Hk of the same order and a graph G that is Hi-convex for all i (1 ≤ i ≤ k). Also, for every connected graph H of order k ≥ 3 with convexity number 2, it is shown that there exists an H-convex graph of order n for all n ≥ k + 1. More generally, it is shown that for every nontrivial connected graph H, there exists a positive integer N and an H-convex graph of order n for every integer n ≥ N.
A 2-stratified graph G is a graph whose vertex set has been partitioned into two subsets, called the strata or color classes of G. Two 2-stratified graphs G and H are isomorphic if there exists a color-preserving isomorphism ϕ from G to H. A 2-stratified graph G is said to be homogeneously embedded in a 2-stratified graph H if for every vertex x of G and every vertex y of H, where x and y are colored the same, there exists an induced 2-stratified subgraph H 0 of H containing y and a color-preserving isomorphism ϕ from G to H0 such that ϕ(x) = y. A 2-stratified graph F of minimum order in which G can be homogeneously embedded is called a frame of G and the order of F is called the framing number fr(G) of G. It is shown that every 2-stratified graph can be homogeneously embedded in some 2-stratified graph. For a graph G, a 2-stratified graph F of minimum order in which every 2-stratification of G can be homogeneously embedded is called a fence of G and the order of F is called the fencing number fe(G) of G. The fencing numbers of some well-known classes of graphs are determined. It is shown that if G is a vertex-transitive graph of order n that is not a complete graph then fe(G) = 2n.
For an ordered $k$-decomposition $\mathcal D = \lbrace G_1, G_2,\dots , G_k\rbrace $ of a connected graph $G$ and an edge $e$ of $G$, the $\mathcal D$-code of $e$ is the $k$-tuple $c_{\mathcal D}(e) = (d(e, G_1), d(e, G_2),\ldots , d(e, G_k))$, where $d(e, G_i)$ is the distance from $e$ to $G_i$. A decomposition $\mathcal D$ is resolving if every two distinct edges of $G$ have distinct $\mathcal D$-codes. The minimum $k$ for which $G$ has a resolving $k$-decomposition is its decomposition dimension $\dim _d(G)$. A resolving decomposition $\mathcal D$ of $G$ is connected if each $G_i$ is connected for $1 \le i \le k$. The minimum $k$ for which $G$ has a connected resolving $k$-decomposition is its connected decomposition number $\mathop {\mathrm cd}(G)$. Thus $2 \le \dim _d(G) \le \mathop {\mathrm cd}(G) \le m$ for every connected graph $G$ of size $m \ge 2$. All nontrivial connected graphs of size $m$ with connected decomposition number 2 or $m$ have been characterized. We present characterizations for connected graphs of size $m$ with connected decomposition number $m-1$ or $m-2$. It is shown that each pair $s, t$ of rational numbers with $ 0 < s \le t \le 1$, there is a connected graph $G$ of size $m$ such that $\dim _d(G)/m = s$ and $\mathop {\mathrm cd}(G) / m = t$.
Let G be a connected graph of order n ≥ 3 and let c : E(G) → {1, 2, . . . , k} be a coloring of the edges of G (where adjacent edges may be colored the same). For each vertex v of G, the color code of v with respect to c is the k-tuple c(v) = (a1, a2, . . . , ak), where ai is the number of edges incident with v that are colored i (1 ≤ i ≤ k). The coloring c is detectable if distinct vertices have distinct color codes. The detection number det(G) of G is the minimum positive integer k for which G has a detectable k-coloring. We establish a formula for the detection number of a path in terms of its order. For each integer n ≥ 3, let Du(n) be the maximum detection number among all unicyclic graphs of order n and du(n) the minimum detection number among all unicyclic graphs of order n. The numbers Du(n) and du(n) are determined for all integers n > 3. Furthermore, it is shown that for integers k ≥ 2 and n ≥ 3, there exists a unicyclic graph G of order n having det(G) = k if and only if du(n) ≤ k ≤ Du(n).
A proper coloring c : V (G) → {1, 2, . . . , k}, k ≥ 2 of a graph G is called a graceful k-coloring if the induced edge coloring c ′ : E(G) → {1, 2, . . . , k − 1} defined by c ′ (uv) = |c(u) − c(v)| for each edge uv of G is also proper. The minimum integer k for which G has a graceful k-coloring is the graceful chromatic number χg(G). It is known that if T is a tree with maximum degree ∆, then χg(T ) ≤ ⌈ 5⁄3∆⌉ and this bound is best possible. It is shown for each integer ∆ ≥ 2 that there is an infinite class of trees T with maximum degree ∆ such that χg(T ) = ⌈ 5⁄3 ∆⌉. In particular, we investigate for each integer ∆ ≥ 2 a class of rooted trees T∆,h with maximum degree ∆ and height h. The graceful chromatic number of T∆,h is determined for each integer ∆ ≥ 2 when 1 ≤ h ≤ 4. Furthermore, it is shown for each ∆ ≥ 2 that lim h→∞ χg(T∆,h) = ⌈ 5⁄3∆⌉.
For a nonempty set S of vertices in a strong digraph D, the strong distance d(S) is the minimum size of a strong subdigraph of D containing the vertices of S. If S contains k vertices, then d(S) is referred to as the k-strong distance of S. For an integer k ≥ 2 and a vertex v of a strong digraph D, the k-strong eccentricity sek(v) of v is the maximum k-strong distance d(S) among all sets S of k vertices in D containing v. The minimum k-strong eccentricity among the vertices of D is its k-strong radius sradk D and the maximum k-strong eccentricity is its k-strong diameter sdiamk D. The k-strong center (k-strong periphery) of D is the subdigraph of D induced by those vertices of k-strong eccentricity sradk(D) (sdiamk(D)). It is shown that, for each integer k ≥ 2, every oriented graph is the k-strong center of some strong oriented graph. A strong oriented graph D is called strongly k-self-centered if D is its own k-strong center. For every integer r ≥ 6, there exist infinitely many strongly 3-self-centered oriented graphs of 3-strong radius r. The problem of determining those oriented graphs that are k-strong peripheries of strong oriented graphs is studied.