共查询到20条相似文献,搜索用时 928 毫秒
1.
Gwang-Yeon Lee 《Linear algebra and its applications》2000,320(1-3):51-61
For a positive integer k2, the k-Fibonacci sequence {gn(k)} is defined as: g1(k)==gk−2(k)=0, gk−1(k)=gk(k)=1 and for n>k2, gn(k)=gn−1(k)+gn−2(k)++gn−k(k). Moreover, the k-Lucas sequence {ln(k)} is defined as ln(k)=gn−1(k)+gn+k−1(k) for n1. In this paper, we consider the relationship between gn(k) and ln(k) and 1-factors of a bipartite graph. 相似文献
2.
Tams Lengyel 《Discrete Mathematics》1996,150(1-3):281-292
We partially characterize the rational numbers x and integers n 0 for which the sum ∑k=0∞ knxk assumes integers. We prove that if ∑k=0∞ knxk is an integer for x = 1 − a/b with a, b> 0 integers and gcd(a,b) = 1, then a = 1 or 2. Partial results and conjectures are given which indicate for which b and n it is an integer if a = 2. The proof is based on lower bounds on the multiplicities of factors of the Stirling number of the second kind, S(n,k). More specifically, we obtain
for all integers k, 2 k n, and a 3, provided a is odd or divisible by 4, where va(m) denotes the exponent of the highest power of a which divides m, for m and a> 1 integers.
New identities are also derived for the Stirling numbers, e.g., we show that ∑k=02nk! S(2n, k) , for all integers n 1. 相似文献
3.
Sergei L. Bezrukov 《Discrete Applied Mathematics》2001,110(2-3):101-119
We consider embeddings of the complete t-ary trees of depth k (denotation Tk,t) as subgraphs into the hypercube of minimum dimension n. This n, denoted by dim(Tk,t), is known if max{k,t}2. First, we study the next open cases t=3 and k=3. We improve the known upper bound dim(Tk,3)2k+1 up to limk→∞dim(Tk,3)/k5/3 and show limt→∞dim(T3,t)/t=227/120. As a co-result, we present an exact formula for the dimension of arbitrary trees of depth 2, as a function of their vertex degrees. These results and new techniques provide an improvement of the known upper bound for dim(Tk,t) for arbitrary k and t. 相似文献
4.
Artur Andrzejak 《Discrete Mathematics》1998,190(1-3):39-54
Let k be a fixed, positive integer. We give an algorithm which computes the Tutte polynomial of any graph G of treewidth at most k in time O(n2+7 log2 c), where c is twice the number of partitions of a set with 3k + 3 elements and n the number of vertices of G. 相似文献
5.
For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number χ(G) = k can be properly vertex colored by k colors so that for each pair of vertices xo and xp in any color class there exist vertices x1, x2, …, xp-1 of the same class with dist(xi, xi+1) f(k) for each i, 0 i p − 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f(k) from the remainder of the class.
We prove that f(k) < 12k when the order of the graph is k(k − 2) + 1. 相似文献
6.
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). 相似文献
7.
A. V. Ivashchenko 《Discrete Mathematics》1993,120(1-3):107-114
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 3n−2 vertices that contains as an induced subgraph a copy of any graph on n vertices. 相似文献
8.
For a graph G of size m1 and edge-induced subgraphs F and H of size k (1km), 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 1km, 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.
Byeong Moon Kim Byung Chul Song Woonjae Hwang 《Linear algebra and its applications》2007,420(2-3):648-662
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. 相似文献
10.
Joel Friedman 《Linear algebra and its applications》1998,280(2-3):199-216
Let A be a positive definite, symmetric matrix. We wish to determine the largest eigenvalue, λ1. We consider the power method, i.e. that of choosing a vector v0 and setting vk = Akv0; then the Rayleigh quotients Rk = (Avk, vk)/(vk, vk) usually converge to λ1 as k → ∞ (here (u, v) denotes their inner product). In this paper we give two methods for determining how close Rk is to λ1. They are both based on a bound on λ1 − Rk involving the difference of two consecutive Rayleigh quotients and a quantity ωk. While we do not know how to directly calculate ωk, we can given an algorithm for giving a good upper bound on it, at least with high probability. This leads to an upper bound for λ1 − Rk which is proportional to (λ2/λ1)2k, which holds with a prescribed probability (the prescribed probability being an arbitrary δ > 0, with the upper bound depending on δ). 相似文献
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 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. 相似文献
13.
Ioan Tomescu 《Discrete Mathematics》1996,150(1-3):453-456
In this paper it is proved that the exponential generating function of the numbers, denoted by N(p, q), of irreducible coverings by edges of the vertices of complete bipartite graphs Kp,q equals exp(xey + yex − x − y − xy) − 1. 相似文献
14.
Matching extension and minimum degree 总被引:1,自引:0,他引:1
Let G be a simple connected graph on 2n vertices with a perfect matching. For a given positive integer k, 1 k n − 1, G is k-extendable if for every matching M of size k in G, there exists a perfect matching in G containing all the edges of M. The problem that arises is that of characterizing k-extendable graphs. In this paper, we establish a necessary condition, in terms of minimum degree, for k-extendable graphs. Further, we determine the set of realizable values for minimum degree of k-extendable graphs. In addition, we establish some results on bipartite graphs including a sufficient condition for a bipartite graph to be k-extendable. 相似文献
15.
Let q*(G) denote the minimum integer t for which E(G) can be partitioned into t induced matchings of G. Faudree et al. conjectured that q*(G)d2, if G is a bipartite graph and d is the maximum degree of G. In this note, we give an affirmative answer for d=3, the first nontrivial case of this conjecture. 相似文献
16.
G. D. Dietz 《Applied Mathematics Letters》2002,15(8):945-953
Let W be an n-dimensional vector space over a field F; for each positive integer m, let the m-tuples (U1, …, Um) of vector subspaces of W be uniformly distributed; and consider the statistics Xm,1 dimF(∑i=1m Ui) and Xm,2 dimF (∩i=1m Ui). If F is finite of cardinality q, we determine lim E(Xm,1k), and lim E(Xm,2k), and hence, lim var(Xm,1) and lim var(Xm,2), for any k > 0, where the limits are taken as q → ∞ (for fixed n). Further, we determine whether these, and other related, limits are attained monotonically. Analogous issues are also addressed for the case of infinite F. 相似文献
17.
J. -F. Sacl 《Discrete Mathematics》1996,150(1-3):359-369
In this paper, we give a lower bound for the size B(n) of a minimum broadcast graph of order n = 2k − 4, 2k − 6, 2k − 5 or 2k − 3 which is shown to be accurate in the cases when k = 5 and k = 6. This result provides, together with an upper bound obtained by a construction given in Bermond et al. (1992), an estimation of the value B(n) for n = 2k − 4. 相似文献
18.
S. Nicoloso 《Discrete Mathematics》2004,280(1-3):251-257
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. 相似文献
19.
Gerard J. Chang Wen-Tsai Ke David Kuo Daphne D. -F. Liu Roger K. Yeh 《Discrete Mathematics》2000,220(1-3):57-66
Given a graph G and a positive integer d, an L(d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then |f(u)−f(v)|d; if u and v are not adjacent but there is a two-edge path between them, then |f(u)−f(v)|1. The L(d,1)-number of G, λd(G), is defined as the minimum m such that there is an L(d,1)-labeling f of G with f(V){0,1,2,…,m}. Motivated by the channel assignment problem introduced by Hale (Proc. IEEE 68 (1980) 1497–1514), the L(2,1)-labeling and the L(1,1)-labeling (as d=2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that λd(G)Δ2+(d−1)Δ for any graph G with maximum degree Δ. Different lower and upper bounds of λd(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs. 相似文献
20.
It has been shown by Lei, in his recent paper, that there exists a large set of Kirkman triple systems of order uv (LKTS(uv)) if there exist an LKTS(v), a TKTS(v) and an LR(u), where a TKTS(v) is a transitive Kirkman triple system of order v, and an LR(u) is a new kind of design introduced by Lei. In this paper, we improve this product construction by removing the condition “there exists a TKTS(v)”. Our main idea is to use transitive resolvable idempotent symmetric quasigroups instead of TKTS. As an application, we can combine the known results on LKTS and LR-designs to obtain the existence of an LKTS(3nm(2·13n1+1)(2·13nt+1)) for n1, m{1,5,11,17,25,35,43,67,91,123}{22r+125s+1 : r0,s0}, t0 and ni1 (i=1,…,t). 相似文献