共查询到20条相似文献,搜索用时 62 毫秒
1.
2.
3.
Given a finite set of 2-dimensional points P⊆R2 and a positive real d, a unit disk graph, denoted by (P,d), is an undirected graph with vertex set P such that two vertices are adjacent if and only if the Euclidean distance between the pair is less than or equal to d. Given a pair of non-negative integers m and n, P(m,n) denotes a subset of 2-dimensional triangular lattice points defined by where . Let Tm,n(d) be a unit disk graph defined on a vertex set P(m,n) and a positive real d. Let be the kth power of Tm,n(1).In this paper, we show necessary and sufficient conditions that [ is perfect] and/or [ is perfect], respectively. These conditions imply polynomial time approximation algorithms for multicoloring (Tm,n(d),w) and . 相似文献
4.
5.
6.
Andreas Weingartner 《Journal of Number Theory》2004,108(1):18-28
Let 1=d1(n)<d2(n)<?<dτ(n)=n be the sequence of all positive divisors of the integer n in increasing order. We say that the divisors of n are t-dense iff max1?i<τ(n)di+1(n)/di(n)?t. Let D(x,t) be the number of positive integers not exceeding x whose divisors are t-dense. We show that for x?3, and , we have , where , and d(w) is a continuous function which satisfies d(w)?1/w for w?1. We also consider other counting functions closely related to D(x,t). 相似文献
7.
8.
9.
Let denote the maximum average degree (over all subgraphs) of G and let χi(G) denote the injective chromatic number of G. We prove that if , then χi(G)≤Δ(G)+1; and if , then χi(G)=Δ(G). Suppose that G is a planar graph with girth g(G) and Δ(G)≥4. We prove that if g(G)≥9, then χi(G)≤Δ(G)+1; similarly, if g(G)≥13, then χi(G)=Δ(G). 相似文献
10.
11.
12.
Ziqin FengPaul Gartside 《Topology and its Applications》2011,158(9):1124-1130
13.
14.
15.
16.
17.
18.
The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p1,p2,…,pn be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p1,p2,…,pn, is obtained by attaching pi new vertices of degree 1 to the vertex ui of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are the thorn graphs of the complete graphs with every . 相似文献
19.
Mark Skandera 《Journal of Pure and Applied Algebra》2008,212(5):1086-1104
Using Du’s characterization of the dual canonical basis of the coordinate ring O(GL(n,C)), we express all elements of this basis in terms of immanants. We then give a new factorization of permutations w avoiding the patterns 3412 and 4231, which in turn yields a factorization of the corresponding Kazhdan-Lusztig basis elements of the Hecke algebra Hn(q). Using the immanant and factorization results, we show that for every totally nonnegative immanant and its expansion with respect to the basis of Kazhdan-Lusztig immanants, the coefficient dw must be nonnegative when w avoids the patterns 3412 and 4231. 相似文献
20.
Mordecai J. Golin 《Discrete Mathematics》2010,310(4):792-803
Let T(G) be the number of spanning trees in graph G. In this note, we explore the asymptotics of T(G) when G is a circulant graph with given jumps.The circulant graph is the 2k-regular graph with n vertices labeled 0,1,2,…,n−1, where node i has the 2k neighbors i±s1,i±s2,…,i±sk where all the operations are . We give a closed formula for the asymptotic limit as a function of s1,s2,…,sk. We then extend this by permitting some of the jumps to be linear functions of n, i.e., letting si, di and ei be arbitrary integers, and examining