Advanced Search

For any vertex v and any edge e in a non-trivial connected graph G, the distance sum d(v) of v is $d\left(v\right)={\sum }_{u\in V}d(v,u)$, the vertex-to-edge distance sum d₁(v) of v is $d₁\left(v\right)={\sum }_{e\in E}d(v,e)$, the edge-to-vertex distance sum d₂(e) of e is $d₂\left(e\right)={\sum }_{v\in V}d(e,v)$ and the edge-to-edge distance sum d₃(e) of e is $d₃\left(e\right)={\sum }_{f\in E}d(e,f)$. The set M(G) of all vertices v for which d(v) is minimum is the median of G; the set M₁(G) of all vertices v for which d₁(v) is minimum is the vertex-to-edge median of G; the set M₂(G) of all edges e for which d₂(e) is minimum is the edge-to-vertex median...

For a connected graph G of order p ≥ 2 and a vertex x of G, a set S ⊆ V(G) is an x-monophonic set of G if each vertex v ∈ V(G) lies on an x -y monophonic path for some element y in S. The minimum cardinality of an x-monophonic set of G is defined as the x-monophonic number of G, denoted by mₓ(G). An x-monophonic set of cardinality mₓ(G) is called a mₓ-set of G. We determine bounds for it and characterize graphs which realize these bounds. A connected graph of order p with vertex monophonic numbers...

For two vertices u and v in a graph G = (V,E), the detour distance D(u,v) is the length of a longest u-v path in G. A u-v path of length D(u,v) is called a u-v detour. A set S ⊆V is called an edge detour set if every edge in G lies on a detour joining a pair of vertices of S. The edge detour number dn₁(G) of G is the minimum order of its edge detour sets and any edge detour set of order dn₁(G) is an edge detour basis of G. A connected graph G is called an edge detour graph if it has an edge detour...

For any vertex x in a connected graph G of order p ≥ 2, a set S of vertices of V is an x-detour set of G if each vertex v in G lies on an x-y detour for some element y in S. A connected x-detour set of G is an x-detour set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected x-detour set of G is the connected x-detour number of G and is denoted by cdₓ(G). For a minimum connected x-detour set Sₓ of G, a subset T ⊆ Sₓ is called a connected x-forcing subset...

For a connected graph G = (V,E), a set W ⊆ V is called a Steiner set of G if every vertex of G is contained in a Steiner W-tree of G. The Steiner number s(G) of G is the minimum cardinality of its Steiner sets and any Steiner set of cardinality s(G) is a minimum Steiner set of G. For a minimum Steiner set W of G, a subset T ⊆ W is called a forcing subset for W if W is the unique minimum Steiner set containing T. A forcing subset for W of minimum cardinality is a minimum forcing subset of W. The...

For a connected graph G = (V,E), a set W ⊆ V is called a Steiner set of G if every vertex of G is contained in a Steiner W-tree of G. The Steiner number s(G) of G is the minimum cardinality of its Steiner sets and any Steiner set of cardinality s(G) is a minimum Steiner set of G. For a minimum Steiner set W of G, a subset T ⊆ W is called a forcing subset for W if W is the unique minimum Steiner set containing T. A forcing subset for W of minimum cardinality is a minimum forcing subset of W. The...

For a connected graph G of order n, a set S of vertices is called a double geodetic set of G if for each pair of vertices x,y in G there exist vertices u,v ∈ S such that x,y ∈ I[u,v]. The double geodetic number dg(G) is the minimum cardinality of a double geodetic set. Any double godetic of cardinality dg(G) is called dg-set of G. The double geodetic numbers of certain standard graphs are obtained. It is shown that for positive integers r,d such that r < d ≤ 2r and 3 ≤ a ≤ b there exists a connected...

For a connected graph G with at least two vertices and S a subset of vertices, the convex hull ${\left[S\right]}_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 ${\left[S\right]}_G=V\left(G\right)$. 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 G and H...

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\left[S\right]={\bigcup }_{x,y\in S}{I}_D[x,y]$. A set S of vertices is a detour convex set if $I_D\left[S\right]=S$. The detour convex hull ${\left[S\right]}_D$ is the smallest detour convex set containing S. The detour hull number dh(G) is the minimum cardinality among subsets S of V(G) with ${\left[S\right]}_D=V\left(G\right)$....

For a nontrivial connected graph G = (V(G),E(G)), a set S⊆ V(G) is called an edge geodetic set of G if every edge of G is contained in a geodesic joining some pair of vertices in S. The edge geodetic number g₁(G) of G is the minimum order of its edge geodetic sets. Bounds for the edge geodetic number of Cartesian product graphs are proved and improved upper bounds are determined for a special class of graphs. Exact values of the edge geodetic number of Cartesian product are obtained for several...

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\left[S\right]$. A set S ⊆ V(G) is a geodetic set if $I_G\left[S\right]=V\left(G\right)$ 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.