首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
The distancedG(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 dG(u,v) is called a (u,v)-geodesic. A set XV is called weakly convex in G if for every two vertices a,bX, exists an (a,b)-geodesic, all of whose vertices belong to X. A set X is convex in G if for all a,bX 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.  相似文献   

2.
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 IG[u,v] denote the set of all vertices lying on a u-v geodesic. Let SV(G) and IG[S] denote the union of all IG[u,v] for all u,vS. A subset SV(G) is a convex set of G if IG[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 IG[S]=V(G). The geodetic number g(G) of a graph G is the minimum cardinality of a geodetic set in G. A subset FV(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 fh(G) of G and the cardinality of a minimum forcing geodetic subset in G is called the forcing geodetic number fg(G) of G. In the paper, we construct some 2-connected graph G with (fh(G),fg(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 (fh(G),fg(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].  相似文献   

3.
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.  相似文献   

4.
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 2 for a nontrivial connected graph H is studied.  相似文献   

5.
Let G be a graph. If u,vV(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 SV(G), the set I[S] is the union of all sets I[u,v] for u,vS. We say that S is a convex set if I[S]=S. The convex hull of S, denoted Ih[S], is the smallest convex set containing S. A set S is a hull set of G if Ih[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.  相似文献   

6.
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 rd, there exists a connected graph G with rad m Gr, diam m Gd and m c (G) =  n. Also, if a,b and p are positive integers such that 2 ≤  ab ≤  p, then there exists a connected graph G of order p, m(G) =  a and m c (G) =  b.  相似文献   

7.
8.
Linda Eroh 《Discrete Mathematics》2008,308(18):4212-4220
Let G be a connected graph and SV(G). Then the Steiner distance of S, denoted by dG(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, dH(S)=dG(S). The eccentricity of a vertex v in a connected graph G is defined as e(v)=max{d(v,x)|xV(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.  相似文献   

9.
《Discrete Applied Mathematics》2002,116(1-2):115-126
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 uv geodesic or vu geodesic in D. For SV(D), I[S] is the union of all closed intervals I[u,v] with u,vS. 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⩽kn−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.  相似文献   

10.
Let G be a graph with vertex set V(G). A set C of vertices of G is g-convex if for every pair \({u, v \in C}\) the vertices on every uv geodesic (i.e. shortest uv path) belong to C. If the only g-convex sets of G are the empty set, V(G), all singletons and all edges, then G is called a g-minimal graph. It is shown that a graph is g-minimal if and only if it is triangle-free and if it has the property that the convex hull of every pair of non-adjacent vertices is V(G). Several properties of g-minimal graphs are established and it is shown that every triangle-free graph is an induced subgraph of a g-minimal graph. Recursive constructions of g-minimal graphs are described and bounds for the number of edges in these graphs are given. It is shown that the roots of the generating polynomials of the number of g-convex sets of each size of a g-minimal graphs are bounded, in contrast to their behaviour over all graphs. A set C of vertices of a graph is m-convex if for every pair \({u, v \in C}\) , the vertices of every induced uv path belong to C. A graph is m-minimal if it has no m-convex sets other than the empty set, the singletons, the edges and the entire vertex set. Sharp bounds on the number of edges in these graphs are given and graphs that are m-minimal are shown to be precisely the 2-connected, triangle-free graphs for which no pair of adjacent vertices forms a vertex cut-set.  相似文献   

11.
For an oriented graph D, let ID[u,v] denote the set of all vertices lying on a u-v geodesic or a v-u geodesic. For SV(D), let ID[S] denote the union of all ID[u,v] for all u,vS. 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 ID[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):DO(G)}, g+(G)=max{g(D):DO(G)}, h(G)=min{h(D):DO(G)}, and h+(G)=max{h(D):DO(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].  相似文献   

12.
Given a graph G=(V,E) and sets L(v) of allowed colors for each vV, a list coloring of G is an assignment of colors φ(v) to the vertices, such that φ(v)∈L(v) for all vV and φ(u)≠φ(v) for all uvE. The choice number of G is the smallest natural number k admitting a list coloring for G whenever |L(v)|≥k holds for every vertex v. This concept has an interesting variant, called Hall number, where an obvious necessary condition for colorability is put as a restriction on the lists L(v). (On complete graphs, this condition is equivalent to the well-known one in Hall’s Marriage Theorem.) We prove that vertex deletion or edge insertion in a graph of order n>3 may make the Hall number decrease by as much as n−3. This estimate is tight for all n. Tightness is deduced from the upper bound that every graph of order n has Hall number at most n−2. We also characterize the cases of equality; for n≥6 these are precisely the graphs whose complements are K2∪(n−2)K1, P4∪(n−4)K1, and C5∪(n−5)K1. Our results completely solve a problem raised by Hilton, Johnson and Wantland [A.J.W. Hilton, P.D. Johnson, Jr., E. B. Wantland, The Hall number of a simple graph, Congr. Numer. 121 (1996), 161-182, Problem 7] in terms of the number of vertices, and strongly improve some estimates due to Hilton and Johnson [A.J.W. Hilton, P.D. Johnson, Jr., The Hall number, the Hall index, and the total Hall number of a graph, Discrete Appl. Math. 94 (1999), 227-245] as a function of maximum degree.  相似文献   

13.
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 SV(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)].  相似文献   

14.
The recently introduced concept of k-power domination generalizes domination and power domination, the latter concept being used for monitoring an electric power system. The k-power domination problem is to determine a minimum size vertex subset S of a graph G such that after setting X=N[S], and iteratively adding to X vertices x that have a neighbour v in X such that at most k neighbours of v are not yet in X, we get X=V(G). In this paper the k-power domination number of Sierpiński graphs is determined. The propagation radius is introduced as a measure of the efficiency of power dominating sets. The propagation radius of Sierpiński graphs is obtained in most of the cases.  相似文献   

15.
Let G(V, E) be a finite, undirected graph, and let l(X) be a set function on 2V. When can the edges of G be oriented so that the indegree of every subset X is at least l(X)? A necessary and sufficient condition is given for the existence of such an orientation when l(X) is “convex”.  相似文献   

16.
Let ω0(G) denote the number of odd components of a graph G. The deficiency of G is defined as def(G)=maxXV(G)(ω0(G-X)-|X|), and this equals the number of vertices unmatched by any maximum matching of G. A subset XV(G) is called a Tutte set (or barrier set) of G if def(G)=ω0(G-X)-|X|, and an extreme set if def(G-X)=def(G)+|X|. Recently a graph operator, called the D-graph D(G), was defined that has proven very useful in examining Tutte sets and extreme sets of graphs which contain a perfect matching. In this paper we give two natural and related generalizations of the D-graph operator to all simple graphs, both of which have analogues for many of the interesting and useful properties of the original.  相似文献   

17.
Let h ≥ 6 be an integer, let G be a 3-connected graph with ∣V(G)∣ ≥ h − 1, and let x and z be distinct vertices of G. We show that if for any nonadjacent distinct vertices u and v in V(G) − {x, z}, the sum of the degrees of u and v in G is greater than or equal to h, then for any subset Y of V(G) − {x, z} with ∣Y∣ ≤ 2, G contains a path which has x and z as its endvertices, passes through all vertices in Y, and has length at least h − 2. We also show a similar result for cycles in 2-connected graphs.  相似文献   

18.
Given a configuration of pebbles on the vertices of a graph G, a pebbling move consists of taking two pebbles off some vertex v and putting one of them back on a vertex adjacent to v. A graph is called pebbleable if for each vertex v there is a sequence of pebbling moves that would place at least one pebble on v. The pebbling number of a graph G is the smallest integer m such that G is pebbleable for every configuration of m pebbles on G. We prove that the pebbling number of a graph of diameter 3 on n vertices is no more than (3/2)n + O(1), and, by explicit construction, that the bound is sharp. © 2006 Wiley Periodicals, Inc. J Graph Theory  相似文献   

19.
Let G be a connected graph with diameter diam(G). The radio number for G, denoted by rn(G), is the smallest integer k such that there exists a function f:V(G)→{0,1,2,…,k} with the following satisfied for all vertices u and v: |f(u)-f(v)|?diam(G)-dG(u,v)+1, where dG(u,v) is the distance between u and v. We prove a lower bound for the radio number of trees, and characterize the trees achieving this bound. Moreover, we prove another lower bound for the radio number of spiders (trees with at most one vertex of degree more than two) and characterize the spiders achieving this bound. Our results generalize the radio number for paths obtained by Liu and Zhu.  相似文献   

20.
A vertex η in a subset X of vertices of an undirected graph is redundant if its closed neighborhood is contained in the union of closed neighborhoods of vertices of X-{η}. In the context of a communications network, this means that any vertex that may receive communications from X may also be informed from X-{η}. The irredundance number ir(G) is the minimum cardinality taken over all maximal sets of vertices having no redundancies. In this note we show that ir(G) ? n/(2Δ-1) for a graph G having n vertices and maximum degree Δ.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号