The forcing hull and forcing geodetic numbers of graphs

For every pair of vertices u,v in a graph, a u-v geodesic is a shortest path from u to v. For a graph G, let I_G[u,v] denote the set of all vertices lying on a u-v geodesic. Let S⊆V(G) and I_G[S] denote the union of all I_G[u,v] for all u,v∈S. A subset S⊆V(G) is a convex set of G if I_G[S]=S. A convex hull [S]_G of S is a minimum convex set containing S. A subset S of V(G) is a hull set of G if [S]_G=V(G). The hull number h(G) of a graph G is the minimum cardinality of a hull set in G. A subset S of V(G) is a geodetic set if I_G[S]=V(G). The geodetic number g(G) of a graph G is the minimum cardinality of a geodetic set in G. A subset F⊆V(G) is called a forcing hull (or geodetic) subset of G if there exists a unique minimum hull (or geodetic) set containing F. The cardinality of a minimum forcing hull subset in G is called the forcing hull number f_h(G) of G and the cardinality of a minimum forcing geodetic subset in G is called the forcing geodetic number f_g(G) of G. In the paper, we construct some 2-connected graph G with (f_h(G),f_g(G))=(0,0),(1,0), or (0,1), and prove that, for any nonnegative integers a, b, and c with a+b≥2, there exists a 2-connected graph G with (f_h(G),f_g(G),h(G),g(G))=(a,b,a+b+c,a+2b+c) or (a,2a+b,a+b+c,2a+2b+c). These results confirm a conjecture of Chartrand and Zhang proposed in [G. Chartrand, P. Zhang, The forcing hull number of a graph, J. Combin. Math. Combin. Comput. 36 (2001) 81-94].     

关于图测地数的几个问题

本文研究了图的测地数.利用极点必属于测地集的方法,刻画了g(G)=n-1的图G的结构,同时使用图的一些重要参数,获得了图上下测地数的几个新的界.对于有向图D,讨论了g(D)=2的充要条件.     

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 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.     

图的下测地数和上测地数

对于图G(或有向图D)内的任意两点u和v,u—v测地线是指在u和v之间(或从u到v)的最短路．I(u,v)表示位于u—v测地线上所有点的集合,对于S(?)V(G)(或V(D)),I(S)表示所有I(u,v)的并,这里u,v∈S．G(或D)的测地数g(G)(或g(D))是使I(S)=V(G)(或I(S)=V(D))的点集S的最小基数．G的下测地数g~-(G)=min{g(D)：D是G的定向图},G的上测地数g~ (G)=max{g(D)：D是G的定向图}．对于u∈V(G)和v∈V(H),G_u H_v表示在u和v之间加一条边所得的图．本文主要研究图G_u H_v的测地数和上(下)测地数．     

Reinforcement numbers of digraphs

The reinforcement number of a graph G is the minimum cardinality of a set of extra edges whose addition results in a graph with domination number less than the domination number of G. In this paper we consider this parameter for digraphs, investigate the relationship between reinforcement numbers of undirected graphs and digraphs, and obtain further results for regular graphs. We also determine the exact values of the reinforcement numbers of de Bruijn digraphs and Kautz digraphs.     

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 the geodetic number and related metric sets in Cartesian product graphs

A set S of vertices of a graph G is a geodetic set if every vertex of G lies in at least one interval between the vertices of S. The size of a minimum geodetic set in G is the geodetic number of G. Upper bounds for the geodetic number of Cartesian product graphs are proved and for several classes exact values are obtained. It is proved that many metrically defined sets in Cartesian products have product structure and that the contour set of a Cartesian product is geodetic if and only if their projections are geodetic sets in factors.     

New proof of a characterization of geodetic graphs

In [3], the present author used a binary operation as a tool for characterizing geodetic graphs. In this paper a new proof of the main result of the paper cited above is presented. The new proof is shorter and simpler.     

Binding numbers for fractional ID-k-factor-critical graphs

LetG be a graph,and k≥2 be a positive integer.A graph G is fractional independentset-deletable k-factor-critical(in short,fractional ID-k-factor-critical),if G I has a fractional k-factor for every independent set I of G.The binding number bind(G)of a graph G is defined as bind(G)=min|NG(X)||X|:=X V(G),NG(X)=V(G).In this paper,it is proved that a graph G is fractional ID-k-factor-critical if n≥6k 9 and bind(G)(3k 1)(n 1)kn 2k+2.     

Small stable generic graphs with infinite weight. Bipartite digraphs

Grounding on Herwig’s generic construction that modifies Hrushovski’s construction, we give some examples of the small stable theories of bipartite digraphs with infinite weight.     

The geodetic number of the lexicographic product of graphs

A set S of vertices of a graph G is a geodetic set if every vertex of G lies in an interval between two vertices from S. The size of a minimum geodetic set in G is the geodetic number g(G) of G. We find that the geodetic number of the lexicographic product G°H for a non-complete graph H lies between 2 and 3g(G). We characterize the graphs G and H for which g(G°H)=2, as well as the lexicographic products T°H that enjoy g(T°H)=3g(G), when T is isomorphic to a tree. Using a new concept of the so-called geodominating triple of a graph G, a formula that expresses the exact geodetic number of G°H is established, where G is an arbitrary graph and H a non-complete graph.     

The diameters of almost all Cayley digraphs

1.IntroductionLetGbeagroupandSasubsetofGnotcontainingtheidentity,1ofG.TheCayleydigraphofGwithrespecttoS,denotedbyX(G,S),isadigraphwhosevertexsetisGandforx,yEG,thereisanarcfromxtoyinX(G,S)ifandonlyifx--laES.IfS=S--',thenX(G,S)isactuallyagraphcalledCayleygraph.ThereisadiversityofliteratureonCnyleygraphsandCayleydigraphs.Themostlyinvestigatedsubjectsaretheconnectivityll'2],theHamiltonianpropertiesl3],theisomorphismsI4]andthediameterIS'6].Recelltly,someauthorsproposedtouseCayleygraph…     

关于Finsler流形中的距离函数与测地球

利用 Finsler流形中的切曲率和旗曲率 ,研究了距离函数与测地球的凸性 ;指出了在单连通完备 Minkowski空间中测地球正好是平面的一部分     

The distribution of the domination number of class cover catch digraphs for non-uniform one-dimensional data

For two or more classes of points in R^d with d≥1, the class cover catch digraphs (CCCDs) can be constructed using the relative positions of the points from one class with respect to the points from one or all of the other classes. The CCCDs were introduced by Priebe et al. [C.E. Priebe, J.G. DeVinney, D.J. Marchette, On the distribution of the domination number of random class catch cover digraphs. Statistics and Probability Letters 55 (2001) 239-246] who investigated the case of two classes, X and Y. They calculated the exact (i.e., finite sample) distribution of the domination number of the CCCDs based on X points relative to Y points both of which were uniformly distributed on a bounded interval. We investigate the distribution of the domination number of the CCCDs based on data from non-uniform X points on an interval with end points from Y. Then we extend these calculations for multiple Y points on bounded intervals.     

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.