Unmixed bipartite graphs and sublattices of the Boolean lattices

The correspondence between unmixed bipartite graphs and sublattices of the Boolean lattice is discussed. By using this correspondence, we show existence of squarefree quadratic initial ideals of toric ideals arising from minimal vertex covers of unmixed bipartite graphs.     

Non-existence of bipartite graphs of diameter at least 4 and defect 2

The Moore bipartite bound represents an upper bound on the order of a bipartite graph of maximum degree Δ and diameter D. Bipartite graphs of maximum degree Δ, diameter D and order equal to the Moore bipartite bound are called Moore bipartite graphs. Such bipartite graphs exist only if D=2,3,4 and 6, and for D=3,4,6, they have been constructed only for those values of Δ such that Δ−1 is a prime power.     

Directed graphs and combinatorial properties of completely regular semigroups

In this paper, we investigate the divisibility graphs and power graphs of completely regular semigroups. We give the structures of these two kinds of graphs and describe a combinatorial property of completely regular semigroups defined in terms of divisibility graphs and power graphs, respectively.     

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.     

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.     

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.      

Several identities for certain products of theta functions

By means of a technique used by Carlitz and Subbarao to prove the quintuple product identity (Proc. Am. Math. Soc. 32(1):42–44, 1972), we recover a general identity (Chu and Yan, Electron. J. Comb. 14:#N7, 2007) for expanding the product of two Jacobi triple products. For applications, we briefly explore identities for certain products of theta functions φ(q), ψ(q) and modular relations for the Göllnitz-Gordon functions.     

An alternative proof of a characterization of Cohen-Macaulay bipartite graphs

Recently, Herzog and Hibi explicitly described all Cohen-Macaulay bipartite graphs by using the Stanley-Reisner ideal of the Alexander dual of the simplicial complex Δ _P associated to a finite poset P. In this paper, we will present a short proof that does not use the Stanley-Reisner ideal of the Alexander dual of Δ _P .     

The genus distributions for a certain type of permutation graphs in orientable surfaces

A circuit is a connected nontrivial 2-regular graph.A graph G is a permutation graph over a circuit C,if G can be obtained from two copies of C by joining these two copies with a perfect matching.In this paper,based on the joint tree method introduced by Liu,the genus polynomials for a certain type of permutation graphs in orientable surfaces are given.     

The geodetic numbers of graphs and digraphs

For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.     

New upper bounds for the independence numbers of graphs with vertices in {−1, 0, 1} n and their applications to problems of the chromatic numbers of distance graphs

Upper bounds for the independence numbers in the graphs with vertices at {?1, 0, 1} ⁿ are improved. Their applications to problems of the chromatic numbers of distance graphs are studied.     

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.