D-saturated property of the Cayley graphs of semigroups

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.     

Independence roots and independence fractals of certain graphs

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.     

A generalization of Eagon–Reiner’s theorem and a characterization of bi-CMt bipartite and chordal graphs

We give a generalization of Eagon-Reiner’s theorem relating Betti numbers of the Stanley-Reisner ideal of a simplicial complex and the CM_t property of its Alexander dual. Then we characterize bi-CM_t bipartite graphs and bi-CM_t chordal graphs. These are generalizations of recent results due to Herzog and Rahimi.     

The proof of Ushio''''s conjecture concerning path factorization of complete bipartite graphs

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.     

P_(4k-1)-factorization of complete bipartite graphs

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.     

Graham’s pebbling conjecture on product of complete bipartite graphs

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.     

The critical groups of a family of graphs and elliptic curves over finite fields

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.     

Combinatorial partitions of finite posets and lattices —Ramsey lattices

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.     

The Randi? index and the diameter of graphs

The Randi? indexR(G) of a graph G is defined as the sum of over all edges uv of G, where d_u and d_v 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 P_n 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.     

Maxima and Minima of the Hosoya Index and the Merrifield-Simmons Index

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.     

A Boolean satisfiability approach to the resource-constrained project scheduling problem

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.     

Results of the maximum genus of graphs

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.     

Edge-decompositions of highly connected graphs into paths

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.      

Kronecker’s limit formula and the height of Euclidean lattices

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.     

Two-party graphs and monotonicity properties of the Poincaré mapping

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.