共查询到20条相似文献,搜索用时 78 毫秒
1.
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. 相似文献
2.
A graph G is locally n-connected (locally n-edge connected) if the neighborhood of each vertex of G is n-connected ( n-edge connected). The local connectivity (local edge-connectivity) of G is the maximum n for which G is locally n-connected (locally n-edge connected). It is shown that if k and m are integers with O k < m, then a graph exists which has connectivity m and local connectivity k. Furthermore, such a graph with smallest order is determined. Corresponding results are obtained involving the local connectivity and the local edge-conectivity. 相似文献
3.
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. 相似文献
4.
Every graph can be represented as the intersection graph on a family of closed unit cubes in Euclidean space En. Cube vertices have integer coordinates. The coordinate matrix, A(G)={ vnk} of a graph G is defined by the set of cube coordinates. The imbedded dimension of a graph, Bp( G), is a number of columns in matrix A(G) such that each of them has at least two distinct elements vnk≠ vpk. We show that Bp( G)=cub( G) for some graphs, and Bp( G) n−2 for any graph G on n vertices. The coordinate matrix uses to obtain the graph U of radius 1 with 3 n−2 vertices that contains as an induced subgraph a copy of any graph on n vertices. 相似文献
5.
It is shown that for every >0 with the probability tending to 1 as n→∞ a random graph G( n,p) contains induced cycles of all lengths k, 3 ≤ k ≤ (1 − ) n log c/c, provided c( n) = ( n − 1) p( n)→∞. 相似文献
6.
Let G be a solvable block transitive automorphism group of a 2−( v,5,1) design and suppose that G is not flag transitive. We will prove that - (1) if G is point imprimitive, then v=21, and GZ21:Z6;
- (2) if G is point primitive, then GAΓL(1,v) and v=pa, where p is a prime number with p≡21 (mod 40), and a an odd integer.
相似文献
7.
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. 相似文献
8.
For a graph G of size m1 and edge-induced subgraphs F and H of size k (1 km), the subgraph H is said to be obtained from F by an edge jump if there exist four distinct vertices u, v, w, and x in G such that uvE( F), wxE( G)− E( F), and H= F− uv+ wx. The minimum number of edge jumps required to transform F into H is the k-jump distance from F to H. For a graph G of size m1 and an integer k with 1 km, the k-jump graph Jk( G) is that graph whose vertices correspond to the edge-induced subgraphs of size k of G and where two vertices of Jk( G) are adjacent if and only if the k-jump distance between the corresponding subgraphs is 1. All connected graphs G for which J2( G) is planar are determined. 相似文献
9.
We prove the following theorem. If G is a connected finite graph of order p, and S is a k-subset of V( G) ( where k≥2), then there is a pair of vertices in S which are at a distance ≤2( p−1)/ k if k does not divide p, and ≤2( p−1)/k + 1 otherwise. 相似文献
10.
Let d, k and n be three integers with k3, d4k−1 and n3 k. We show that if d( x)+ d( y) d for each pair of nonadjacent vertices x and y of a graph G of order n, then G contains k vertex-disjoint cycles converting at least min{ d, n} vertices of G. 相似文献
11.
A graph G = ( V, E) on n vertices is primitive if there is a positive integer k such that for each pair of vertices u, v of G, there is a walk of length k from u to v. The minimum value of such an integer, k, is the exponent, exp( G), of G. In this paper, we find the minimum number, h( n, k), of edges of a simple graph G on n vertices with exponent k, and we characterize all graphs which have h( n, k) edges when k is 3 or even. 相似文献
12.
We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R( G,ρ)/ F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D( R( G,ρ)/ F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2 k2, in which the route degree is
, the total number of routes is O( k2n) and D( R( G,λ)/ F)3 for any fault set F (| F|< k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is
, the total number of routes is O( n) and D( R( G,λ′)/{ f})3 for any fault f. We also show that we can construct a routing ρ 1 for every n-node biconnected graph, in which the total number of routes is O( n) and D( R( G,ρ 1)/{ f})2 for any fault f, and a routing ρ 2 (using ρ 1) for every n-node biconnected graph, in which the route degree is
, the total number of routes is
and D( R( G,ρ 2)/{ f})2 for any fault f. 相似文献
13.
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. 相似文献
14.
For a positive integer k, a k-subdominating function of a graph G=( V, E) is a function f : V→{−1,1} such that ∑ uNG[v]f( u)1 for at least k vertices v of G. The k-subdomination number of G, denoted by γ ks( G), is the minimum of ∑ vVf( v) taken over all k-subdominating functions f of G. In this article, we prove a conjecture for k-subdomination on trees proposed by Cockayne and Mynhardt. We also give a lower bound for γ ks( G) in terms of the degree sequence of G. This generalizes some known results on the k-subdomination number γ ks( G), the signed domination number γ s( G) and the majority domination number γ maj( G). 相似文献
15.
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. 相似文献
16.
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. 相似文献
17.
A graph G = G( V, E) with lists L( v), associated with its vertices v V, is called L-list colourable if there is a proper vertex colouring of G in which the colour assigned to a vertex v is chosen from L( v). We say G is k- choosable if there is at least one L-list colouring for every possible list assignment L with L( v) = k v V( G). Now, let an arbitrary vertex v of G be coloured with an arbitrary colour f of L(v). We investigate whether the colouring of v can be continued to an L-list colouring of the whole graph. G is called free k-choosable if such an L-list colouring exists for every list assignment L (L(v) = k v V(G)), every vertex v and every colour f L(v). We prove the equivalence of the well-known conjecture of Erd
s et al. (1979): “Every planar graph is 5-choosable” with the following conjecture: “Every planar graph is free 5-choosable”. 相似文献
18.
Let G be an infinite locally finite connected graph. We study the reconstructibility of G in relation to the structure of its end set
. We prove that an infinite locally finite connected graph G is reconstructible if there exists a finite family (Ωi)0i (n2) of pairwise finitely separable subsets of
such that, for all x, y, x′, y′ V( G) and every isomorphism f of G−{ x, y} onto G−{ x′, y′} there is a permutation π of {0,…, n−1} such that
for 0 i< n. From this theorem we deduce, as particular consequences, that G is reconstructible if it satisfies one of the following properties: (i) G contains no end-respecting subdivision of the dyadic tree and has at least two ends of maximal order; (ii) the set of thick ends or the one of thin ends of G is finite and of cardinality greater than one. We also prove that if almost all vertices of G are cutvertices, then G is reconstructible if it contains a free end or if it has at least a vertex which is not a cutvertex. 相似文献
19.
A labeling of a graph is a function f from the vertex set to some subset of the natural numbers. The image of a vertex is called its label. We assign the label | f( u)− f( v)| to the edge incident with vertices u and v. In a k-equitable labeling the image of f is the set {0,1,2,…, k−1}. We require both the vertex labels and the edge labels to be as equally distributed as possible, i.e., if vi denotes the number of vertices labeled i and ei denotes the number of edges labeled i, we require | vi− vj|1 and | ei− ej|1 for every i, j in {0,1,2,…, k−1}. Equitable graph labelings were introduced by I. Cahit as a generalization for graceful labeling. We prove that every tree is 3-equitable. 相似文献
20.
The problem of constructing ( m, n) cages suggests the following class of problems. For a graph parameter θ, determine the minimum or maximum value of p for which there exists a k-regular graph on p points having a given value of θ. The minimization problem is solved here when θ is the achromatic number, denoted by ψ. This result follows from the following main theorem. Let M( p, k) be the maximum value of ψ( G) over all k-regular graphs G with p points, let { x} be the least integer of size at least x, and let
be given by ω( k) = { i( ik+1)+1:1 i<∞}. Define the function ƒ( p, k) by . Then for fixed k2 we have M( p, K=ƒ( p, k) if pω( k) and M( p, k)=ƒ(p, k-1 if pε ω( k) for all p sufficiently large with respect to k. 相似文献
|