The strong metric dimension of graphs and digraphs

Let G be a connected (di)graph. A vertex w is said to strongly resolve a pair u,v of vertices of G if there exists some shortest u-w path containing v or some shortest v-w path containing u. A set W of vertices is a strong resolving set for G if every pair of vertices of G is strongly resolved by some vertex of W. The smallest cardinality of a strong resolving set for G is called the strong dimension of G. It is shown that the problem of finding the strong dimension of a connected graph can be transformed to the problem of finding the vertex covering number of a graph. Moreover, it is shown that computing this invariant is NP-hard. Related invariants for directed graphs are defined and studied.     

Resolvability in circulant graphs

A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, v ∈ V (G) there is a vertex w ∈ W such that d(u, w) ≠ d(v, w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim(G). For a vertex u of G and a subset S of V (G), the distance between u and S is the number min s∈S d(u, s). A k-partition Π = {S 1 , S 2 , . . . , S k } of V (G) is called a resolving partition if for every two distinct vertices u, v ∈ V (G) there is a set S i in Π such that d(u, Si )≠ d(v, Si ). The minimum k for which there is a resolving k-partition of V (G) is called the partition dimension of G, denoted by pd(G). The circulant graph is a graph with vertex set Zn , an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i-j (mod n) ∈ C , where CZn has the property that C =-C and 0 ■ C. The circulant graph is denoted by Xn, Δ where Δ = |C|. In this paper, we study the metric dimension of a family of circulant graphs Xn, 3 with connection set C = {1, n/2 , n-1} and prove that dim(Xn, 3 ) is independent of choice of n by showing that dim(Xn, 3 ) ={3 for all n ≡ 0 (mod 4), 4 for all n ≡ 2 (mod 4). We also study the partition dimension of a family of circulant graphs Xn,4 with connection set C = {±1, ±2} and prove that pd(Xn, 4 ) is independent of choice of n and show that pd(X5,4 ) = 5 and pd(Xn,4 ) ={3 for all odd n ≥ 9, 4 for all even n ≥ 6 and n = 7.     

Some properties onf-edge covered critical graphs

LetG(V, E) be a simple graph, and letf be an integer function onV with 1 ≤f(v) ≤d(v) to each vertexv ∈V. An f-edge cover-coloring of a graphG is a coloring of edge setE such that each color appears at each vertexv ∈V at leastf(v) times. Thef-edge cover chromatic index ofG, denoted by χ′ _fc (G), is the maximum number of colors such that anf-edge cover-coloring ofG exists. Any simple graphG has anf-edge cover chromatic index equal to δ_f or δ _f - 1, where $\delta _f = \mathop {\min }\limits_{\upsilon \in V} \{ \left\lfloor {\frac{{d(v)}}{{f(v)}}} \right\rfloor \} $ . LetG be a connected and not complete graph with χ′ _fc (G)=δ _f-1, if for eachu, v ∈V and e =uv ?E, we have ÷ _fc (G + e) > ÷ _fc (G), thenG is called anf-edge covered critical graph. In this paper, some properties onf-edge covered critical graph are discussed. It is proved that ifG is anf-edge covered critical graph, then for eachu, v ∈V and e =uv ?E there existsw ∈ {u, v } withd(w) ≤ δ _f (f(w) + 1) - 2 such thatw is adjacent to at leastd(w) - δ _f + 1 vertices which are all δ _f -vertex inG.     

The Connected Monophonic Number of a Graph

For a connected graph G = (V, E) of order at least two, a chord of a path P is an edge joining two non-adjacent vertices of P. A path P is called a monophonic path if it is a chordless path. A set S of vertices of G is a monophonic set of G if each vertex v of G lies on an x ? y monophonic path for some elements x and y in S. The minimum cardinality of a monophonic set of G is defined as the monophonic number of G, denoted by m(G). A connected monophonic set of G is a monophonic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected monophonic set of G is the connected monophonic number of G and is denoted by m _c (G). We determine bounds for it and characterize graphs which realize these bounds. For any two vertices u and v in G, the monophonic distance d _m (u, v) from u to v is defined as the length of a longest u ? v monophonic path in G. The monophonic eccentricity e _m (v) of a vertex v in G is the maximum monophonic distance from v to a vertex of G. The monophonic radius rad _m G of G is the minimum monophonic eccentricity among the vertices of G, while the monophonic diameter diam _m G of G is the maximum monophonic eccentricity among the vertices of G. It is shown that for positive integers r, d and n ≥ 5 with r <  d, there exists a connected graph G with rad _m G =  r, diam _m G =  d and m _c (G) =  n. Also, if a,b and p are positive integers such that 2 ≤  a <  b ≤  p, then there exists a connected graph G of order p, m(G) =  a and m _c (G) =  b.     

On the maximal eccentric connectivity indices of graphs

For a connected simple graph G, the eccentricity ec(v) of a vertex v in G is the distance from v to a vertex farthest from v, and d(v) denotes the degree of a vertex v. The eccentric connectivity index of G, denoted by ξc(G), is defined as v∈V(G)d(v)ec(v). In this paper, we will determine the graphs with maximal eccentric connectivity index among the connected graphs with n vertices and m edges(n ≤ m ≤ n + 4), and propose a conjecture on the graphs with maximal eccentric connectivity index among the connected graphs with n vertices and m edges(m ≥ n + 5).     

Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs

Let G be a connected graph and S⊆V(G). Then the Steiner distance of S, denoted by d_G(S), is the smallest number of edges in a connected subgraph of G containing S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval for a set S of vertices in a graph, denoted by I(S) is the union of all vertices that belong to some Steiner tree for S. If S={u,v}, then I(S) is the interval I[u,v] between u and v. A connected graph G is 3-Steiner distance hereditary (3-SDH) if, for every connected induced subgraph H of order at least 3 and every set S of three vertices of H, d_H(S)=d_G(S). The eccentricity of a vertex v in a connected graph G is defined as e(v)=max{d(v,x)|x∈V(G)}. A vertex v in a graph G is a contour vertex if for every vertex u adjacent with v, e(u)?e(v). The closure of a set S of vertices, denoted by I[S], is defined to be the union of intervals between pairs of vertices of S taken over all pairs of vertices in S. A set of vertices of a graph G is a geodetic set if its closure is the vertex set of G. The smallest cardinality of a geodetic set of G is called the geodetic number of G and is denoted by g(G). A set S of vertices of a connected graph G is a Steiner geodetic set for G if I(S)=V(G). The smallest cardinality of a Steiner geodetic set of G is called the Steiner geodetic number of G and is denoted by sg(G). We show that the contour vertices of 3-SDH and HHD-free graphs are geodetic sets. For 3-SDH graphs we also show that g(G)?sg(G). An efficient algorithm for finding Steiner intervals in 3-SDH graphs is developed.     

The Sigma Chromatic Number of a Graph

For a nontrivial connected graph G, let ${c: V(G)\to {{\mathbb N}}}For a nontrivial connected graph G, let c: V(G)? \mathbb N{c: V(G)\to {{\mathbb N}}} be a vertex coloring of G, where adjacent vertices may be colored the same. For a vertex v of G, let N(v) denote the set of vertices adjacent to v. The color sum σ(v) of v is the sum of the colors of the vertices in N(v). If σ(u) ≠ σ(v) for every two adjacent vertices u and v of G, then c is called a sigma coloring of G. The minimum number of colors required in a sigma coloring of a graph G is called its sigma chromatic number σ(G). The sigma chromatic number of a graph G never exceeds its chromatic number χ(G) and for every pair a, b of positive integers with a ≤ b, there exists a connected graph G with σ(G) = a and χ(G) = b. There is a connected graph G of order n with σ(G) = k for every pair k, n of positive integers with k ≤n if and only if k ≠ n − 1. Several other results concerning sigma chromatic numbers are presented.     

The 2-pebbling property for dense graphs

Given a distribution of pebbles on the vertices of a connected graph G, a pebbling move on G consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The pebbling number f(G) is the smallest number m such that for every distribution of m pebbles and every vertex v,a pebble can be moved to v. A graph G is said to have the 2-pebbling property if for any distribution with more than 2f(G) q pebbles, where q is the number of vertices with at least one pebble, it is possible,using pebbling moves, to get two pebbles to any vertex. Snevily conjectured that G(s,t) has the 2-pebbling property, where G(s, t) is a bipartite graph with partite sets of size s and t (s ≥ t). Similarly, the-pebbling number f (G) is the smallest number m such that for every distribution of m pebbles and every vertex v, pebbles can be moved to v. Herscovici et al. conjectured that f(G) ≤ 1.5n + 8-6 for the graph G with diameter 3, where n = |V (G)|. In this paper, we prove that if s ≥ 15 and G(s, t) has minimum degree at least (s+1)/ 2 , then f (G(s, t)) = s + t, G(s, t) has the 2-pebbling property and f (G(s, t)) ≤ s + t + 8(-1). In other words, we extend a result due to Czygrinow and Hurlbert, and show that the above Snevily conjecture and Herscovici et al. conjecture are true for G(s, t) with s ≥ 15 and minimum degree at least (s+1)/ 2 .     

Conditional Resolvability of Honeycomb and Hexagonal Networks

Given a graph G = (V, E), a set W í V{W \subseteq V} is said to be a resolving set if for each pair of distinct vertices u, v ? V{u, v \in V} there is a vertex x in W such that d(u, x) 1 d(v, x){d(u, x) \neq d(v, x)} . The resolving number of G is the minimum cardinality of all resolving sets. In this paper, conditions are imposed on resolving sets and certain conditional resolving parameters are studied for honeycomb and hexagonal networks.     

Convexity in oriented graphs

For vertices u and v in an oriented graph D, the closed interval I[u,v] consists of u and v together with all vertices lying in a u−v geodesic or v−u geodesic in D. For S⊆V(D), I[S] is the union of all closed intervals I[u,v] with u,v∈S. A set S is convex if I[S]=S. The convexity number con(D) is the maximum cardinality of a proper convex set of V(D). The nontrivial connected oriented graphs of order n with convexity number n−1 are characterized. It is shown that there is no connected oriented graph of order at least 4 with convexity number 2 and that every pair k, n of integers with 1⩽k⩽n−1 and k≠2 is realizable as the convexity number and order, respectively, of some connected oriented graph. For a nontrivial connected graph G, the lower orientable convexity number con⁻(G) is the minimum convexity number among all orientations of G and the upper orientable convexity number con⁺(G) is the maximum such convexity number. It is shown that con⁺(G)=n−1 for every graph G of order n⩾2. The lower orientable convexity numbers of some well-known graphs are determined, with special attention given to outerplanar graphs.     

Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs

A Steiner tree for a set S of vertices in a connected graph G is a connected subgraph of G with a smallest number of edges that contains S. The Steiner interval I(S) of S is the union of all the vertices of G that belong to some Steiner tree for S. If S={u,v}, then I(S)=I[u,v] is called the interval between u and v and consists of all vertices that lie on some shortest u-v path in G. The smallest cardinality of a set S of vertices such that ?_u,v∈SI[u,v]=V(G) is called the geodetic number and is denoted by g(G). The smallest cardinality of a set S of vertices of G such that I(S)=V(G) is called the Steiner geodetic number of G and is denoted by sg(G). We show that for distance-hereditary graphs g(G)?sg(G) but that g(G)/sg(G) can be arbitrarily large if G is not distance hereditary. An efficient algorithm for finding the Steiner interval for a set of vertices in a distance-hereditary graph is described and it is shown how contour vertices can be used in developing an efficient algorithm for finding the Steiner geodetic number of a distance-hereditary graph.     

Degree Distance of Unicyclic Graphs with Given Matching Number

Let G be a connected graph with vertex set V(G). The degree distance of G is defined as ${D'(G) = \sum_{\{u, v\}\subseteq V(G)} (d_G(u) + d_G (v))\, d(u,v)}$ , where d _G (u) is the degree of vertex u, d(u, v) denotes the distance between u and v, and the summation goes over all pairs of vertices in G. In this paper, we characterize n-vertex unicyclic graphs with given matching number and minimal degree distance.     

A note on the weakly convex and convex domination numbers of a torus

The distanced_G(u,v) between two vertices u and v in a connected graph G is the length of the shortest (u,v) path in G. A (u,v) path of length d_G(u,v) is called a (u,v)-geodesic. A set X⊆V is called weakly convex in G if for every two vertices a,b∈X, exists an (a,b)-geodesic, all of whose vertices belong to X. A set X is convex in G if for all a,b∈X all vertices from every (a,b)-geodesic belong to X. The weakly convex domination number of a graph G is the minimum cardinality of a weakly convex dominating set of G, while the convex domination number of a graph G is the minimum cardinality of a convex dominating set of G. In this paper we consider weakly convex and convex domination numbers of tori.     

Graph Equation for Line Graphs and m-Step Graphs

Given a graph G, the m-step graph of G, denoted by S _m (G), has the same vertex set as G and an edge between two distinct vertices u and v if there is a walk of length m from u to v. The line graph of G, denoted by L(G), is a graph such that the vertex set of L(G) is the edge set of G and two vertices u and v of L(G) are adjacent if the edges corresponding to u and v share a common end vertex in G. We characterize connected graphs G such that S _m (G) and L(G) are isomorphic.     

Nordhaus-Gaddum results for the convex domination number of a graph

The distance d _G (u, v) between two vertices u and v in a connected graph G is the length of the shortest uv-path in G. A uv-path of length d _G (u, v) is called a uv-geodesic. A set X is convex in G if vertices from all ab-geodesics belong to X for any two vertices a, b ?? X. The convex domination number ??_con(G) of a graph G equals the minimum cardinality of a convex dominating set. In the paper, Nordhaus-Gaddum-type results for the convex domination number are studied.     

Signed k-independence in graphs

Let k ≥ 2 be an integer. A function f: V(G) → {?1, 1} defined on the vertex set V(G) of a graph G is a signed k-independence function if the sum of its function values over any closed neighborhood is at most k ? 1. That is, Σ _x∈N[v] f(x) ≤ k ? 1 for every v ∈ V(G), where N[v] consists of v and every vertex adjacent to v. The weight of a signed k-independence function f is w(f) = Σ _v∈V(G) f(v). The maximum weight w(f), taken over all signed k-independence functions f on G, is the signed k-independence number α _s ^k (G) of G. In this work, we mainly present upper bounds on α _s ^k (G), as for example α _s ^k (G) ≤ n ? 2?(Δ(G) + 2 ? k)/2?, and we prove the Nordhaus-Gaddum type inequality $\alpha _S^k \left( G \right) + \alpha _S^k \left( {\bar G} \right) \leqslant n + 2k - 3$ , where n is the order, Δ(G) the maximum degree and $\bar G$ the complement of the graph G. Some of our results imply well-known bounds on the signed 2-independence number.     

The upper traceable number of a graph

For a nontrivial connected graph G of order n and a linear ordering s: v ₁, v ₂, …, v _n of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t ⁺(G) of G is t ⁺(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs G for which t ⁺(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established. Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand under the grant number MRG 5080075.     

An Improved Upper Bound on the Total Restrained Domination Number in Cubic Graphs

In this paper, we continue the study of total restrained domination in graphs. A set S of vertices in a graph G = (V, E) is a total restrained dominating set of G if every vertex of G is adjacent to some vertex in S and every vertex of ${V {\setminus} S}$ is adjacent to a vertex in ${V {\setminus} S}$ . The minimum cardinality of a total restrained dominating set of G is the total restrained domination number γ _tr(G) of G. Jiang et?al. (Graphs Combin 25:341–350, 2009) showed that if G is a connected cubic graph of order n, then γ _tr(G) ≤ 13n/19. In this paper we improve this upper bound to γ _tr(G) ≤ (n?+?4)/2. We provide two infinite families of connected cubic graphs G with γ _tr(G) = n/2, showing that our new improved bound is essentially best possible.     

Graphs with small diameter determined by their <Emphasis Type="Italic">D</Emphasis>-spectra

Let G be a connected graph with vertex set V(G) = {v₁, v₂,..., v _n }. The distance matrix D(G) = (d _ij )_n×n is the matrix indexed by the vertices of G, where d _ij denotes the distance between the vertices v _i and v _j . Suppose that λ₁(D) ≥ λ₂(D) ≥... ≥ λ _n (D) are the distance spectrum of G. The graph G is said to be determined by its D-spectrum if with respect to the distance matrix D(G), any graph having the same spectrum as G is isomorphic to G. We give the distance characteristic polynomial of some graphs with small diameter, and also prove that these graphs are determined by their D-spectra.