The upper connected geodetic number and forcing connected geodetic number of a graph

For a connected graph G of order p≥2, a set S⊆V(G) is a geodetic set of G if each vertex v∈V(G) lies on an x-y geodesic for some elements x and y in S. The minimum cardinality of a geodetic set of G is defined as the geodetic number of G, denoted by g(G). A geodetic set of cardinality g(G) is called a g-set of G. A connected geodetic set of G is a geodetic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected geodetic set of G is the connected geodetic number of G and is denoted by g_c(G). A connected geodetic set of cardinality g_c(G) is called a g_c-set of G. A connected geodetic set S in a connected graph G is called a minimal connected geodetic set if no proper subset of S is a connected geodetic set of G. The upper connected geodetic number is the maximum cardinality of a minimal connected geodetic set of G. We determine bounds for and determine the same for some special classes of graphs. For positive integers r,d and n≥d+1 with r≤d≤2r, there exists a connected graph G with , and . Also, for any positive integers 2≤a<b≤c, there exists a connected graph G such that g(G)=a, g_c(G)=b and . A subset T of a g_c-set S is called a forcing subset for S if S is the unique g_c-set containing T. A forcing subset for S of minimum cardinality is a minimum forcing subset of S. The forcing connected geodetic number of S, denoted by f_c(S), is the cardinality of a minimum forcing subset of S. The forcing connected geodetic number of G, denoted by f_c(G), is f_c(G)=min{f_c(S)}, where the minimum is taken over all g_c-sets S in G. It is shown that for every pair a,b of integers with 0≤a≤b−4, there exists a connected graph G such that f_c(G)=a and g_c(G)=b.     

The Forcing Convexity Number of a Graph

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 S is denoted by I(S). A set S is a convex set if I(S) = S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. A convex set S in G with |S| = con(G) 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 containing T. The forcing convexity number f(S, con) of S is the minimum cardinality among the forcing subsets for S, and the forcing convexity number f(G, con) of G is the minimum forcing convexity number among all maximum convex sets of G. The forcing convexity numbers of several classes of graphs are presented, including complete bipartite graphs, trees, and cycles. For every graph G, f(G, con) con(G). It is shown that every pair a, b of integers with 0 a b and b is realizable as the forcing convexity number and convexity number, respectively, of some connected graph. The forcing convexity number of the Cartesian product of H × K ₂ for a nontrivial connected graph H is studied.     

The lower and upper forcing geodetic numbers of block–cactus graphs

A vertex set D in graph G is called a geodetic set if all vertices of G are lying on some shortest u–v path of G, where u, v ∈ D. The geodetic number of a graph G is the minimum cardinality among all geodetic sets. A subset S of a geodetic set D is called a forcing subset of D if D is the unique geodetic set containing S. The forcing geodetic number of D is the minimum cardinality of a forcing subset of D, and the lower and the upper forcing geodetic numbers of a graph G are the minimum and the maximum forcing geodetic numbers, respectively, among all minimum geodetic sets of G. In this paper, we find out the lower and the upper forcing geodetic numbers of block–cactus graphs.     

The hull and geodetic numbers of orientations of graphs

For an oriented graph D, let I_D[u,v] denote the set of all vertices lying on a u-v geodesic or a v-u geodesic. For S⊆V(D), let I_D[S] denote the union of all I_D[u,v] for all u,v∈S. Let [S]_D denote the smallest convex set containing S. The geodetic number g(D) of an oriented graph D is the minimum cardinality of a set S with I_D[S]=V(D) and the hull number h(D) of an oriented graph D is the minimum cardinality of a set S with [S]_D=V(D). For a connected graph G, let O(G) be the set of all orientations of G, define g⁻(G)=min{g(D):D∈O(G)}, g⁺(G)=max{g(D):D∈O(G)}, h⁻(G)=min{h(D):D∈O(G)}, and h⁺(G)=max{h(D):D∈O(G)}. By the above definitions, h⁻(G)≤g⁻(G) and h⁺(G)≤g⁺(G). In the paper, we prove that g⁻(G)<h⁺(G) for a connected graph G of order at least 3, and for any nonnegative integers a and b, there exists a connected graph G such that g⁻(G)−h⁻(G)=a and g⁺(G)−h⁺(G)=b. These results answer a problem of Farrugia in [A. Farrugia, Orientable convexity, geodetic and hull numbers in graphs, Discrete Appl. Math. 148 (2005) 256-262].     

The geodetic numbers of graphs and digraphs

For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.     

On the computation of the hull number of a graph

Let G be a graph. If u,v∈V(G), a u-vshortest path of G is a path linking u and v with minimum number of edges. The closed interval I[u,v] consists of all vertices lying in some u-v shortest path of G. For S⊆V(G), the set I[S] is the union of all sets I[u,v] for u,v∈S. We say that S is a convex set if I[S]=S. The convex hull of S, denoted I_h[S], is the smallest convex set containing S. A set S is a hull set of G if I_h[S]=V(G). The cardinality of a minimum hull set of G is the hull number of G, denoted by hn(G). In this work we prove that deciding whether hn(G)≤k is NP-complete.We also present polynomial-time algorithms for computing hn(G) when G is a unit interval graph, a cograph or a split graph.     

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.     

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.     

A note on Roman domination in graphs

Let G=(V,E) be a simple graph. A subset S⊆V is a dominating set of G, if for any vertex u∈V-S, there exists a vertex v∈S such that uv∈E. The domination number of G, γ(G), equals the minimum cardinality of a dominating set. A Roman dominating function on graph G=(V,E) is a function f:V→{0,1,2} satisfying the condition that every vertex v for which f(v)=0 is adjacent to at least one vertex u for which f(u)=2. The weight of a Roman dominating function is the value f(V)=∑_v∈Vf(v). The Roman domination number of a graph G, denoted by γ_R(G), equals the minimum weight of a Roman dominating function on G. In this paper, for any integer k(2?k?γ(G)), we give a characterization of graphs for which γ_R(G)=γ(G)+k, which settles an open problem in [E.J. Cockayne, P.M. Dreyer Jr, S.M. Hedetniemi et al. On Roman domination in graphs, Discrete Math. 278 (2004) 11-22].     

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.     

Signed star domatic number of a graph

Let G be a simple graph without isolated vertices with vertex set V(G) and edge set E(G). A function f:E(G)?{−1,1} is said to be a signed star dominating function on G if ∑_e∈E(v)f(e)≥1 for every vertex v of G, where E(v)={uv∈E(G)∣u∈N(v)}. A set {f₁,f₂,…,f_d} of signed star dominating functions on G with the property that for each e∈E(G), is called a signed star dominating family (of functions) on G. The maximum number of functions in a signed star dominating family on G is the signed star domatic number of G, denoted by d_SS(G).In this paper we study the properties of the signed star domatic number d_SS(G). In particular, we determine the signed domatic number of some classes of graphs.     

Extreme Geodesic Graphs

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 of G, while for S V(G), the set I[S] is the union of all sets I[u, v] for u, v 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 ex(G). A graph G is an extreme geodesic graph if g(G) = ex(G), that is, if every vertex lies on a u–v geodesic for some pair u, v of extreme vertices. It is shown that every pair a, b of integers with 0 a b is realizable as the extreme order and geodetic number, respectively, of some graph. For positive integers r, d, and k 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 d > n, 2 k > n, and n – d – k + 1 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 k n – 2, there exists a connected graph of order n with geodetic number k that is not an extreme geodesic graph.     

On forcing matching number of boron-nitrogen fullerene graphs

Let G be a graph that admits a perfect matching M. A forcing set S for a perfect matching M is a subset of M such that it is contained in no other perfect matchings of G. The smallest cardinality of forcing sets of M is called the forcing number of M. Computing the minimum forcing number of perfect matchings of a graph is an NP-complete problem. In this paper, we consider boron-nitrogen (BN) fullerene graphs, cubic 3-connected plane bipartite graphs with exactly six square faces and other hexagonal faces. We obtain the forcing spectrum of tubular BN-fullerene graphs with cyclic edge-connectivity 3. Then we show that all perfect matchings of any BN-fullerene graphs have the forcing number at least two. Furthermore, we mainly construct all seven BN-fullerene graphs with the minimum forcing number two.     

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.     

Some results on exclusive sum graphs

Let N(Z) denote the set of all positive integers (integers). The sum graph G ⁺(S) of a finite subset S?N(Z) is the graph (S,E) with uv∈E if and only if u+v∈S. A graph G is said to be an (integral) sum graph if it is isomorphic to the sum graph of some S?N(Z). A sum labelling S is called an exclusive sum labelling if u+v∈S?V(G) for any edge uv∈E(G). We say that G is labeled exclusively. The least number r of isolated vertices such that G∪rK ₁ is an exclusive sum graph is called the exclusive sum number ε(G) of graph G. In this paper, we discuss the exclusive sum number of disjoint union of two graphs and the exclusive sum number of some graph classes.     

On distance two graphs of upper bound graphs

For a poset P=(X,≤), the upper bound graph (UB-graph) of P is the graph U=(X,E_U), where uv∈E_U if and only if u≠v and there exists m∈X such that u,v≤m. For a graph G, the distance two graph DS₂(G) is the graph with vertex set V(DS₂(G))=V(G) and u,v∈V(DS₂(G)) are adjacent if and only if d_G(u,v)=2. In this paper, we deal with distance two graphs of upper bound graphs. We obtain a characterization of distance two graphs of split upper bound graphs.     

Complexity results related to monophonic convexity

The study of monophonic convexity is based on the family of induced paths of a graph. The closure of a subset X of vertices, in this case, contains every vertex v such that v belongs to some induced path linking two vertices of X. Such a closure is called monophonic closure. Likewise, the convex hull of a subset is called monophonic convex hull. In this work we deal with the computational complexity of determining important convexity parameters, considered in the context of monophonic convexity. Given a graph G, we focus on three parameters: the size of a maximum proper convex subset of G (m-convexity number); the size of a minimum subset whose closure is equal to V(G) (monophonic number); and the size of a minimum subset whose convex hull is equal to V(G) (m-hull number). We prove that the decision problems corresponding to the m-convexity and monophonic numbers are NP-complete, and we describe a polynomial time algorithm for computing the m-hull number of an arbitrary graph.     

Labeling bipartite permutation graphs with a condition at distance two

An L(p,q)-labeling of a graph G is an assignment f from vertices of G to the set of non-negative integers {0,1,…,λ} such that |f(u)−f(v)|≥p if u and v are adjacent, and |f(u)−f(v)|≥q if u and v are at distance 2 apart. The minimum value of λ for which G has L(p,q)-labeling is denoted by λ_p,q(G). The L(p,q)-labeling problem is related to the channel assignment problem for wireless networks.In this paper, we present a polynomial time algorithm for computing L(p,q)-labeling of a bipartite permutation graph G such that the largest label is at most (2p−1)+q(bc(G)−2), where bc(G) is the biclique number of G. Since λ_p,q(G)≥p+q(bc(G)−2) for any bipartite graph G, the upper bound is at most p−1 far from optimal.     

On geodetic sets formed by boundary vertices

Let G be a finite simple connected graph. A vertex v is a boundary vertex of G if there exists a vertex u such that no neighbor of v is further away from u than v. We obtain a number of properties involving different types of boundary vertices: peripheral, contour and eccentric vertices. Before showing that one of the main results in [G. Chartrand, D. Erwin, G.L. Johns, P. Zhang, Boundary vertices in graphs, Discrete Math. 263 (2003) 25-34] does not hold for one of the cases, we establish a realization theorem that not only corrects the mentioned wrong statement but also improves it.Given S⊆V(G), its geodetic closure I[S] is the set of all vertices lying on some shortest path joining two vertices of S. We prove that the boundary vertex set ∂(G) of any graph G is geodetic, that is, I[∂(G)]=V(G). A vertex v belongs to the contour Ct(G) of G if no neighbor of v has an eccentricity greater than v. We present some sufficient conditions to guarantee the geodeticity of either the contour Ct(G) or its geodetic closure I[Ct(G)].     

On the geodetic number of permutation graphs

A vertex set S in a graph G is a geodetic set if every vertex of G lies on some u?v geodesic of G, where u,v∈S. The geodetic number g(G) of G is the minimum cardinality over all geodetic sets of G. Let G ₁ and G ₂ be disjoint copies of a graph G, and let σ:V(G ₁)→V(G ₂) be a bijection. Then, a permutation graph G _σ =(V,E) has the vertex set V=V(G ₁)∪V(G ₂) and the edge set E=E(G ₁)∪E(G ₂)∪{uv∣v=σ(u)}. For any connected graph G of order n≥3, we prove the sharp bounds 2≤g(G _σ )≤2n?(1+△(G)), where △(G) denotes the maximum degree of G. We give examples showing that neither is there a function h ₁ such that g(G)<h ₁(g(G _σ )) for all pairs (G,σ), nor is there a function h ₂ such that h ₂(g(G))>g(G _σ ) for all pairs (G,σ). Further, we characterize permutation graphs G _σ satisfying g(G _σ )=2|V(G)|?(1+△(G)) when G is a cycle, a tree, or a complete k-partite graph.