共查询到20条相似文献,搜索用时 15 毫秒
1.
Let Z denote the set of all integers. The integral sum graph of a finite subset S of Z is the graph ( S, E) with vertex set S and edge set E such that for u, vS, uvE if and only if u+ vS. A graph G is called an integral sum graph if it is isomorphic to the integral sum graph of some finite subset S of Z. The integral sum number of a given graph G, denoted by ζ( G), is the smallest number of isolated vertices which when added to G result in an integral sum graph. Let x denote the least integer not less than the real x. In this paper, we (i) determine the value of ζ( Kn− E( Kr)) for r2 n/3−1, (ii) obtain a lower bound for ζ( Kn− E( Kr)) when 2 r<2 n/3−1 and n5, showing by construction that the bound is sharp when r=2, and (iii) determine the value of ζ( Kr,r) for r2. These results provide partial solutions to two problems posed by Harary (Discrete Math. 124 (1994) 101–108). Finally, we furnish a counterexample to a result on the sum number of Kr,s given by Hartsfiedl and Smyth (Graphs and Matrices, R. Rees (Ed.), Marcel, Dekker, New York, 1992, pp. 205–211). 相似文献
2.
The SUM COLORING problem consists of assigning a color c( vi) Z+ to each vertex viV of a graph G=( V, E) so that adjacent nodes have different colors and the sum of the c( vi)'s over all vertices viV is minimized. In this note we prove that the number of colors required to attain a minimum valued sum on arbitrary interval graphs does not exceed min{ n;2χ( G)−1}. Examples from the papers [Discrete Math. 174 (1999) 125; Algorithmica 23 (1999) 109] show that the bound is tight. 相似文献
3.
The metric dimension dim(G)of a graph G is the minimum number of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices.The zero forcing number Z(G)of a graph G is the minimum cardinality of a set S of black vertices(whereas vertices in V(G)\S are colored white)such that V(G)is turned black after finitely many applications of"the color-change rule":a white vertex is converted black if it is the only white neighbor of a black vertex.We show that dim(T)≤Z(T)for a tree T,and that dim(G)≤Z(G)+1 if G is a unicyclic graph;along the way,we characterize trees T attaining dim(T)=Z(T).For a general graph G,we introduce the"cycle rank conjecture".We conclude with a proof of dim(T)-2≤dim(T+e)≤dim(T)+1 for e∈E(T). 相似文献
4.
Given graph G=( V, E) on n vertices, the profile minimization problem is to find a one-to-one function f: V→{1,2,…, n} such that ∑ vV(G){ f( v)−min xN[v] f( x)} is as small as possible, where N[ v]={ v}{ x: x is adjacent to v} is the closed neighborhood of v in G. The trangulated triangle Tl is the graph whose vertices are the triples of non-negative integers summing to l, with an edge connecting two triples if they agree in one coordinate and differ by 1 in the other two coordinates. This paper provides a polynomial time algorithm to solve the profile minimization problem for trangulated triangles Tl with side-length l. 相似文献
5.
A graph G is said to be n- factor-critical if G− S has a 1-factor for any SV( G) with | S|= n. In this paper, we prove that if G is a 2-connected n-factor-critical graph of order p with
, then G is hamiltonian with some exceptions. To extend this theorem, we define a ( k, n)- factor-critical graph to be a graph G such that G− S has a k-factor for any SV( G) with | S|= n. We conjecture that if G is a 2-connected ( k, n)-factor-critical graph of order p with
, then G is hamiltonian with some exceptions. In this paper, we characterize all such graphs that satisfy the assumption, but are not 1-tough. Using this, we verify the conjecture for k2. 相似文献
6.
A graph is called supereulerian if it has a spanning closed trail. Let G be a 2-edge-connected graph of order n such that each minimal edge cut SE( G) with | S|3 satisfies the property that each component of G− S has order at least ( n−2)/5. We prove that either G is supereulerian or G belongs to one of two classes of exceptional graphs. Our results slightly improve earlier results of Catlin and Li. Furthermore, our main result implies the following strengthening of a theorem of Lai within the class of graphs with minimum degree δ4: If G is a 2-edge-connected graph of order n with δ( G)4 such that for every edge xyE( G) , we have max{ d( x), d( y)}( n−2)/5−1, then either G is supereulerian or G belongs to one of two classes of exceptional graphs. We show that the condition δ( G)4 cannot be relaxed. 相似文献
7.
A graph G with n vertices is said to be embeddable (in its complement) if there is an automorphism φ of Kn such that E( G) ∩ E(φ( G))=. It is known that all trees T with n (≥2) vertices and T K1,n−1 are embeddable. We say that G is 1-embeddable if, for every edge e, there is an automorphism φ of Kn such that E( G) ∩ E(φ( G))={ e};and that it is 2-embeddable if,for every pair e1, e2 of edges, there is an automorphism φ of Kn such that E( G) ∩ E(φ( G))={ e1, e2}. We prove here that all trees with n (3) vertices are 1-embeddable; and that all trees T with n (4) vertices and T K1,n−1 are 2-embeddable. In a certain sense, this result is sharp. 相似文献
8.
Let G be a graph of order n, and let a and b be integers such that 1 a< b. Let δ( G) be the minimum degree of G. Then we prove that if δ( G)( k−1) a, n( a+ b)( k( a+ b)−2)/ b, and | NG( x1) NG( x2) NG( xk)| an/( a+ b) for any independent subset { x1, x2,…, xk} of V( G), where k2, then G has an [ a, b]-factor. This result is best possible in some sense. 相似文献
9.
A graph G is said to be cyclable if for each orientation
of G, there exists a set S of vertices such that reversing all the arcs of
with one end in S results in a hamiltonian digraph. Let G be a 3-connected graph of order n36. In this paper, we show that if for any three independent vertices x1, x2 and x3, | N( x1) N( x2)|+| N( x2) N( x3)|+| N( x3) N( x1)|2 n+1, then G is cyclable. 相似文献
10.
The chromatic difference sequence cds( G) of a graph G with chromatic number n is defined by cds( G) = ( a(1), a(2),…, a( n)) if the sum of a(1), a(2),…, a( t) is the maximum number of vertices in an induced t-colorable subgraph of G for t = 1, 2,…, n. The Cartesian product of two graphs G and H, denoted by G□ H, has the vertex set V( G□ H = V( G) x V( H) and its edge set is given by ( x1, y1)( x2, y2) ε E( G□ H) if either x1 = x2 and y1 y2 ε E( H) or y1 = y2 and x1x2 ε E( G). We obtained four main results: the cds of the product of bipartite graphs, the cds of the product of graphs with cds being nondrop flat and first-drop flat, the non-increasing theorem for powers of graphs and cds of powers of circulant graphs. 相似文献
11.
A k-connected graph G is said to be critically k-connected if G− v is not k-connected for any vV( G). We show that if n, k are integers with k4 and nk+2, and G is a critically k-connected graph of order n, then | E( G)| n( n−1)/2− p( n− k)+ p2/2, where p=( n/ k)+1 if n/ k is an odd integer and p= n/ k otherwise. We also characterize extremal graphs. 相似文献
12.
A simple undirected graph H is called a sum graph if there is a labeling L of the vertices of H into distinct positive integers such that any two vertices u and v of H are adjacent if and only if there is a vertex w with label L( w)= L( u)+ L( v). The sum number σ( G) of a graph G=( V, E) is the least integer r such that the graph H consisting of G and r isolated vertices is a sum graph. It is clear that σ( G)| E|. In this paper, we discuss general upper and lower bounds on the sum number. In particular, we prove that, over all graphs G=( V, E) with fixed | V|3 and | E|, the average of σ( G) is at least . In other words, for most graphs, σ( G)Ω(| E|). 相似文献
13.
An L(2,1)- coloring of a graph G is a coloring of G's vertices with integers in {0,1,…, k} so that adjacent vertices’ colors differ by at least two and colors of distance-two vertices differ. We refer to an L(2,1)-coloring as a coloring. The span λ( G) of G is the smallest k for which G has a coloring, a span coloring is a coloring whose greatest color is λ( G), and the hole index ρ( G) of G is the minimum number of colors in {0,1,…,λ( G)} not used in a span coloring. We say that G is full-colorable if ρ( G)=0. More generally, a coloring of G is a no-hole coloring if it uses all colors between 0 and its maximum color. Both colorings and no-hole colorings were motivated by channel assignment problems. We define the no-hole span μ( G) of G as ∞ if G has no no-hole coloring; otherwise μ( G) is the minimum k for which G has a no-hole coloring using colors in {0,1,…, k}. Let n denote the number of vertices of G, and let Δ be the maximum degree of vertices of G. Prior work shows that all non-star trees with Δ3 are full-colorable, all graphs G with n=λ(G)+1 are full-colorable, μ(G)λ(G)+ρ(G) if G is not full-colorable and nλ(G)+2, and G has a no-hole coloring if and only if nλ(G)+1. We prove two extremal results for colorings. First, for every m1 there is a G with ρ(G)=m and μ(G)=λ(G)+m. Second, for every m2 there is a connected G with λ(G)=2m, n=λ(G)+2 and ρ(G)=m. 相似文献
14.
A dominating set for a graph G = ( V, E) is a subset of vertices V′ V such that for all v ε V − V′ there exists some u ε V′ for which { v, u} ε E. The domination number of G is the size of its smallest dominating set(s). For a given graph G with minimum size dominating set D, let m1 ( G, D) denote the number of edges that have neither endpoint in D, and let m2 ( G, D) denote the number of edges that have at least one endpoint in D. We characterize the possible values that the pair ( m1 ( G, D), m2 ( G, D)) can attain for connected graphs having a given domination number. 相似文献
15.
In a circular permutation diagram, there are two sets of terminals on two concentric circles: Cin and Cout. Given a permutation Π = [π 1, π 2, …, π n], terminal i on Cin and terminal π i on Cout are connected by a wire. The intersection graph Gc of a circular permutation diagram Dc is called a circular permutation graph of a permutation Π corresponding to the diagram Dc. The set of all circular permutation graphs of a permutation Π is called the circular permutation graph family of permutation Π. In this paper, we propose the following: (1) an O( V + E) time algorithm to check if a labeled graph G = ( V, E) is a labeled circular permutation graph. (2) An O( n log n + nt) time algorithm to find a maximum independent set of a family, where n = Π and t is the cardinality of the output. (Number t in the worst case is O( n). However, if Π is uniformly distributed (and independent from i), its expected value is O(√ n).) (3) An O(min(δ Vclog log Vc, Vclog Vc) + Ec) time algorithm for finding a maximum independent set of a circular permutation diagram Dc, where δ is the minimum degree of vertices in the intersection graph Gc = ( Vc, Ec) of Dc. (4) An O( n log log n) time algorithm for finding a maximum clique and the chromatic number of a circular permutation diagram, where n is the number of wires in the diagram. 相似文献
16.
For any positive integer n and any graph G a set D of vertices of G is a distance- n dominating set, if every vertex vV( G)− D has exactly distance n to at least one vertex in D. The distance- n domination number γ =n( G) is the smallest number of vertices in any distance- n dominating set. If G is a graph of order p and each vertex in G has distance n to at least one vertex in G, then the distance- n domination number has the upper bound p/2 as Ore's upper bound on the classical domination number. In this paper, a characterization is given for graphs having distance- n domination number equal to half their order, when the diameter is greater or equal 2 n−1. With this result we confirm a conjecture of Boland, Haynes, and Lawson. 相似文献
17.
Path–distance–width of a graph G=( V, E), denoted by pdw( G), is the minimum integer k satisfying that there is a nonempty subset of SV such that the number of the nodes with distance i from S is at most k for any nonnegative integer i. It is known that given a positive integer k and a graph G, the decision problem pdw( G) k is NP-complete even if G is a tree (Yamazaki et al. Lecture Notes in Computer Science, vol. 1203, Springer, Berlin, 1997, pp. 276–287). In this paper, we show that it is NP-hard to approximate the path–distance–width of a graph within a ratio
for any >0, even for trees. 相似文献
18.
Integrity, a measure of network reliability, is defined as where G is a graph with vertex set V and m( G− S) denotes the order of the largest component of G− S. We prove an upper bound of the following form on the integrity of any cubic graph with n vertices: Moreover, there exist an infinite family of connected cubic graphs whose integrity satisfies a linear lower bound I( G)>β n for some constant β. We provide a value for β, but it is likely not best possible. To prove the upper bound we first solve the following extremal problem. What is the least number of vertices in a cubic graph whose removal results in an acyclic graph? The solution (with a few minor exceptions) is that n/3 vertices suffice and this is best possible. 相似文献
19.
For two edge-induced subgraphs F and H of the same size in a graph G, the subgraph H can be obtained from F by an edge jump if there exist four distinct vertices u, v, w, and x in G such that uv ε E( F), wx ε E( G) - E( F), and H = F - uv + wx. The subgraph F is j-transformed into H if H can be obtained from F by a sequence of edge jumps. Necessary and sufficient conditions are presented for a graph G to have the property that every edge-induced subgraph of a fixed size in G can be j-transformed into every other edge-induced subgraph of that size. The minimum number of edge jumps required to transform one subgraph into another is called the jump distance. This distance is a metric and can be modeled by a graph. The jump graph J( G) of a graph G is defined as that graph whose vertices are the edges of G and where two vertices of J( G) are adjacent if and only if the corresponding edges of G are independent. For a given graph G, we consider the sequence {{ Jk( G)}} of iterated jump graphs and classify each graph as having a convergent, divergent, or terminating sequence. 相似文献
20.
Let G be a graph with vertex set V ( G), edge set E( G) and maximum degree Δ respectively. G is called degree-magic if it admits a labelling of the edges by integers {1, 2, …,| E( G)|} such that for any vertex v the sum of the labels of the edges incident with v is equal to (1+| E( G)|)/2· d( v), where d( v) is the degree of v. Let f be a proper edge coloring of G such that for each vertex v ∈ V ( G),|{ e:e ∈ Ev, f( e) ≤ Δ/2}|=|{ e:e ∈ Ev, f( e) > Δ/2}|, and such an f is called a balanced edge coloring of G. In this paper, we show that if G is a supermagic even graph with a balanced edge coloring and m ≥ 1, then (2 m + 1) G is a supermagic graph. If G is a d-magic even graph with a balanced edge coloring and n ≥ 2, then nG is a d-magic graph. Results in this paper generalise some known results. 相似文献
|