共查询到20条相似文献,搜索用时 15 毫秒
1.
Let D be a finite graph. A semigroup S is said to be Cayley D-saturated with respect to a subset T of S if, for all infinite subsets V of S, there exists a subgraph of Cay(S,T) isomorphic to D with all vertices in V. The purpose of this paper is to characterize the Cayley D-saturated property of a semigroup S with respect to any subset T⊆S. In particular, the Cayley D-saturated property of a semigroup S with respect to any subsemigroup T is characterized. 相似文献
2.
3.
The independence polynomial of a graph G is the polynomial ∑i k x k , where i k denote the number of independent sets of cardinality k in G. In this paper, we obtain the relationships between the independence polynomial of path P n and cycle C n with Jacobsthal polynomial. We find all roots of Jacobsthal polynomial. As a consequence, the roots of independence polynomial of the family {P n } and {C n } are real and dense in $(-\infty,-\frac{1}{4}]$ . Also we investigate the independence fractals or independence attractors of paths, cycles, wheels and certain trees. 相似文献
4.
We give a generalization of Eagon-Reiner’s theorem relating Betti numbers of the Stanley-Reisner ideal of a simplicial complex and the CMt property of its Alexander dual. Then we characterize bi-CMt bipartite graphs and bi-CMt chordal graphs. These are generalizations of recent results due to Herzog and Rahimi. 相似文献
5.
6.
DU Beiliang & WANG Jian Department of Mathematics Suzhou University Suzhou China Nantong Vocational College Nantong China 《中国科学A辑(英文版)》2006,49(3)
Let Km,n be a complete bipartite graph with two partite sets having m and n vertices, respectively. A Pv-factorization of Km,n is a set of edge-disjoint Pv-factors of Km,n which partition the set of edges of Km,n. When v is an even number, Wang and Ushio gave a necessary and sufficient condition for existence of Pv-factorization of Km,n. When k is an odd number, Ushio in 1993 proposed a conjecture. Very recently, we have proved that Ushio's conjecture is true when v = 4k-1. In this paper we shall show that Ushio Conjecture is true when v = 4k 1, and then Ushio's conjecture is true. That is, we will prove that a necessary and sufficient condition for the existence of a P4k 1-factorization of Km,n is (i) 2km≤ (2k 1)n, (ii) 2kn≤ (2k 1)m, (iii) m n = 0 (mod 4k 1), (iv) (4k 1)mn/[4k(m n)] is an integer. 相似文献
7.
8.
DU Beiliang & WANG Jian Department of Mathematics Suzhou University Suzhou China Nantong Vocational College Nantong China 《中国科学A辑(英文版)》2005,48(4)
Let Km,n be a complete bipartite graph with two partite sets having m and n vertices, respectively. A Pv-factorization of Km,n is a set of edge-disjoint pv-factors of Km,n which partition the set of edges of Km,n. When v is an even number, Wang and Ushio gave a necessary and sufficient condition for the existence of Pv-factorization of Km,n.When v is an odd number, Ushio in 1993 proposed a conjecture. However, up to now we only know that Ushio Conjecture is true for v = 3. In this paper we will show that Ushio Conjecture is true when v = 4k - 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P4k-1-factorization of Km,n is (1) (2k - 1)m ≤ 2kn, (2) (2k -1)n≤2km, (3) m n ≡ 0 (mod 4k - 1), (4) (4k -1)mn/[2(2k -1)(m n)] is an integer. 相似文献
9.
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 moves, each move taking two pebbles off one vertex and placing one on
an adjacent vertex. Graham conjectured that for any connected graphs G and H, f( G x H) ⩽ f( G) f( H). We show that Graham’s
conjecture holds true of a complete bipartite graph by a graph with the two-pebbling property. As a corollary, Graham’s conjecture
holds when G and H are complete bipartite graphs. 相似文献
10.
Gregg Musiker 《Journal of Algebraic Combinatorics》2009,30(2):255-276
Let q be a power of a prime, and E be an elliptic curve defined over
. Such curves have a classical group structure, and one can form an infinite tower of groups by considering E over field extensions
for all k≥1. The critical group of a graph may be defined as the cokernel of L(G), the Laplacian matrix of G. In this paper, we compare elliptic curve groups with the critical groups of a certain family of graphs. This collection
of critical groups also decomposes into towers of subgroups, and we highlight additional comparisons by using the Frobenius
map of E over
.
This work was partially supported by the NSF, grant DMS-0500557 during the author’s graduate school at the University of California,
San Diego, and partially supported by an NSF Postdoctoral Fellowship. 相似文献
11.
12.
It is proved that for every finite latticeL there exists a finite latticeL such that for every partition of the points ofL into two classes there exists a lattice embeddingf:LL such that the points off(L) are in one of the classes.This property is called point-Ramsey property of the class of all finite lattices. In fact a stronger theorem is proved which implies the following: for everyn there exists a finite latticeL such that the Hasse-diagram (=covering relation) has chromatic number >n. We discuss the validity of Ramseytype theorems in the classes of finite posets (where a full discussion is given) and finite distributive lattices. Finally we prove theorems which deal with partitions of lattices into an unbounded number of classes.Presented by G. Grätzer. 相似文献
13.
The Randi? indexR(G) of a graph G is defined as the sum of over all edges uv of G, where du and dv are the degrees of vertices u and v, respectively. Let D(G) be the diameter of G when G is connected. Aouchiche et al. (2007) [1] conjectured that among all connected graphs G on n vertices the path Pn achieves the minimum values for both R(G)/D(G) and R(G)−D(G). We prove this conjecture completely. In fact, we prove a stronger theorem: If G is a connected graph, then , with equality if and only if G is a path with at least three vertices. 相似文献
14.
15.
The Hosoya index and the Merrifield-Simmons index are typical examples of graph invariants used in mathematical chemistry
for quantifying relevant details of molecular structure. In recent years, quite a lot of work has been done on the extremal
problem for these two indices, i.e., the problem of determining the graphs within certain prescribed classes that maximize
or minimize the index value. This survey collects and classifies these results, and also provides some useful auxiliary results,
tools and techniques that are frequently used in the study of this type of problem. 相似文献
16.
Andrei Horbach 《Annals of Operations Research》2010,181(1):89-107
We formulate the resource-constrained project scheduling problem as a satisfiability problem and adapt a satisfiability solver
for the specific domain of the problem. Our solver is lightweight and shows good performance both in finding feasible solutions
and in proving lower bounds. Our numerical tests allowed us to close several benchmark instances of the RCPSP that have never
been closed before by proving tighter lower bounds and by finding better feasible solutions. Using our method we solve optimally
more instances of medium and large size from the benchmark library PSPLIB and do it faster compared to any other existing
solver. 相似文献
17.
Guang-hua DONG~ Yan-pei LIU Department of Mathematics School of Science Beijing Jiaotong University Beijing China 《中国科学A辑(英文版)》2007,50(11):1563-1570
In this paper,we provide a new class of up-embeddable graphs,and obtain a tight lower bound on the maximum genus of a class of 2-connected pseudographs of diameter 2 and of a class of diameter 4 multi-graphs.This extends a result of Skoviera. 相似文献
18.
Carsten Thomassen 《Abhandlungen aus dem Mathematischen Seminar der Universit?t Hamburg》2008,78(1):17-26
We prove that a graph of edge-connectivity at least
has an edge-decomposition into paths of length 4 if and only its size is divisible by 4. We also prove that a graph of girth
>m and of edge-connectivity at least 8
m
has an edge-decomposition into paths of length m provided its size is divisible by m, and m is a power of 2.
相似文献
19.
Giovanni Lazzarini 《Archiv der Mathematik》2016,106(4):327-335
The height \({h(\Lambda)}\) of a Euclidean lattice \({\Lambda}\) is defined as the derivative at the point 0 of the spectral zeta function of the associated flat torus \({{\bf R}^n /\Lambda}\). The quest of the lattices which realise a minimum of h is an open problem in dimension higher than 3. In this paper, we show that a lattice which realises a local minimum of the height is irreducible, i.e. it cannot be decomposed into the orthogonal sum of two non-zero sublattices. The proof is based on a formula found by Terras, which generalises Kronecker’s limit formula for the Epstein zeta function. 相似文献
20.
The local differential of a system of nonlinear differential equations with a T-periodic right-hand side is representable as a directed sign interaction graph. Within the class of balanced graphs, where all paths between two fixed vertices have the same signs, it is possible to estimate the sign structure of the differential of the global Poincaré mapping (a shift in time T). In this case all vertices of a strongly connected graph naturally break into two sets (two parties). As appeared, the influence of variables within one party is positive, while that of variables from different parties is negative. Even having simplified the structure of a local two-party graph (by eliminating its edges), one can still exactly describe the sign structure of the differential of the Poincaré mapping. The obtained results are applicable in the mathematical competition theory. 相似文献