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.
A graph $G$ is degree-continuous if the degrees of every two adjacent vertices of $G$ differ by at most 1. A finite nonempty set $S$ of integers is convex if $k \in S$ for every integer $k$ with $\min (S) \le k \le \max (S)$. It is shown that for all integers $r > 0$ and $s \ge 0$ and a convex set $S$ with $\min (S) = r$ and $\max (S) = r+s$, there exists a connected degree-continuous graph $G$ with the degree set $S$ and diameter $2s+2$. The minimum order of a degree-continuous graph with a prescribed degree set is studied. Furthermore, it is shown that for every graph $G$ and convex set $S$ of positive integers containing the integer 2, there exists a connected degree-continuous graph $H$ with the degree set $S$ and containing $G$ as an induced subgraph if and only if $\max (S)\ge \Delta (G)$ and $G$ contains no $r-$regular component where $r = \max (S)$.
The diameter of a graph G is the maximal distance between two vertices of G. A graph G is said to be diameter-edge-invariant, if d(G−e) = d(G) for all its edges, diametervertex-invariant, if d(G − v) = d(G) for all its vertices and diameter-adding-invariant if d(G + e) = d(e) for all edges of the complement of the edge set of G. This paper describes some properties of such graphs and gives several existence results and bounds for parameters of diameter-invariant graphs.
We investigated the effect of the feeding behaviour of young larvae of Pieris rapae crucivora Boisduval (Pieridae) on parasitism by the parasitoid wasp, Cotesia glomerata (L.) (Braconidae). Young, 1st-3rd instar larvae used approximately three sites for feeding each day. When not feeding, they moved a short distance away from the feeding sites (= feeding marks) and rested. For first, second and third instar larvae, the distances from the new mark, made within 24 h, to larva at rest were, respectively, about 3.5 mm, 5 mm and more than 10 mm. To resume feeding, they moved back to one of the former feeding sites or a new site. The percentage of the feeding marks older than 24 h that attracted parasitoids was less than 50%. Time spent searching for hosts by a parasitoid was short. Larvae placed 5 mm or more from a feeding mark were less parasitized than the larvae placed near a mark. The number of feeding marks affected parasitism. When comparing single-marked and triple-marked leaves, the percentage parasitism of the larvae on the latter was significantly lower than that of the larvae on the former. On triple-marked leaves, parasitoids visited each mark unevenly. Accordingly, the time spent searching each mark differed significantly among the marks. Because of this confusing effect, hosts are considered to be reducing the risk of parasitism. Our results demonstrate that the feeding habits of young larvae of P. rapae crucivora are adaptive in terms of reducing the risk of parasitism by C. glomerata., Aya Nakayama, Keiji Nakamura, Jun Tagawa., and Obsahuje bibliografii
The eccentricity e(v) of a vertex v is the distance from v to a vertex farthest from v, and u is an eccentric vertex for v if its distance from v is d(u, v) = e(v). A vertex of maximum eccentricity in a graph G is called peripheral, and the set of all such vertices is the peripherian, denoted PeriG). We use Cep(G) to denote the set of eccentric vertices of vertices in C(G). A graph G is called an S-graph if Cep(G) = Peri(G). In this paper we characterize S-graphs with diameters less or equal to four, give some constructions of • S-graphs and investigate S-graphs with one central vertex. We also correct and generalize some results of F. Gliviak.
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$.
If $G$ is a connected graph with distance function $d$, then by a step in $G$ is meant an ordered triple $(u, x, v)$ of vertices of $G$ such that $d(u, x) = 1$ and $d(u, v) = d(x, v) + 1$. A characterization of the set of all steps in a connected graph was published by the present author in 1997. In Section 1 of this paper, a new and shorter proof of that characterization is presented. A stronger result for a certain type of connected graphs is proved in Section 2.
The reverse Wiener index of a connected graph $G$ is defined as \[ \Lambda (G)=\frac {1}{2}n(n-1)d-W(G), \] where $n$ is the number of vertices, $d$ is the diameter, and $W(G)$ is the Wiener index (the sum of distances between all unordered pairs of vertices) of $G$. We determine the $n$-vertex non-starlike trees with the first four largest reverse Wiener indices for $n\ge 8$, and the $n$-vertex non-starlike non-caterpillar trees with the first four largest reverse Wiener indices for $n\ge 10$.
A radio antipodal coloring of a connected graph G with diameter d is an assignment of positive integers to the vertices of G, with x ∈ V (G) assigned c(x), such that d(u, v) + |c(u) − c(v)| ≥ d for every two distinct vertices u, v of G, where d(u, v) is the distance between u and v in G. The radio antipodal coloring number ac(c) of a radio antipodal coloring c of G is the maximum color assigned to a vertex of G. The radio antipodal chromatic number ac(G) of G is min{ac(c)} over all radio antipodal colorings c of G. Radio antipodal chromatic numbers of paths are discussed and upper and lower bounds are presented. Furthermore, upper and lower bounds for radio antipodal chromatic numbers of graphs are given in terms of their diameter and other invariants.
For an ordered set W = {w1, w2, . . . , wk} of vertices in a connected graph G and a vertex v of G, the code of v with respect to W is the k-vector cW (v) = (d(v, w1), d(v, w2), . . . , d(v, wk)). The set W is an independent resolving set for G if (1) W is independent in G and (2) distinct vertices have distinct codes with respect to W. The cardinality of a minimum independent resolving set in G is the independent resolving number ir(G). We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs G of order n with ir(G) = 1, n − 1, n − 2, and present several realization results. It is shown that for every pair r, k of integers with k ≥ 2 and 0 ≤ r ≤ k, there exists a connected graph G with ir(G) = k such that exactly r vertices belong to every minimum independent resolving set of G.