Super-edge-graceful Labelings of Some Cubic Graphs

The notion of super-edge-graceful graphs was introduced by Mitchem and Simoson in 1994.However, few examples except trees are known. In this paper, we exhibit two classes of infinitely many cubic graphs which are super-edge-graceful. A conjecture is proposed.

L(j,k)-number of Direct Product of Path and Cycle

For positive numbers j and k, an L（j,k）-labeling f of G is an assignment of numbers to vertices of G such that ｜f（u）-f（v）｜≥j if uv∈E（G）, and ｜f（u）-f（v）｜≥k if d（u,v）=2. Then the span of f is the difference between the maximum and the minimum numbers assigned by f. The L（j,k）-number of G, denoted by λj,k（G）, is the minimum span over all L（j,k）-labelings of G. In this paper, we give some results about the L（j,k）-number of the direct product of a path and a cycle for j≤k.

Graphs Whose Critical Groups Have Larger Rank

The critical group C（G） of a graph G is a refinement of the number of spanning trees of the graph and is closely connected with the Laplacian matrix. Let r（G） be the minimum number of generators （i.e., the rank） of the group C（G） and β（G） be the number of independent cycles of G. In this paper, some forbidden induced subgraphs axe given for r（G） = n - 3 and all graphs with r（G） = j3（G） = n - 3 are characterized

Full Friendly Index Sets of Cartesian Products of Two Cycles

Let G =（V, E） be a connected simple graph. A labeling f ： V → Z2 induces an edge labeling f＊ ： E → Z2 defined by f＊（xy） = f（x） ＋f（y） for each xy ∈ E. For i ∈ Z2, let vf（i） = ｜f^-1（i）｜ and ef（i） = ｜f＊^-1（i）｜. A labeling f is called friendly if ｜vf（1） - vf（0）｜ ≤ 1. For a friendly labeling f of a graph G, we define the friendly index of G under f by if（G） = e（1） - el（0）. The set [if（G） ｜ f is a friendly labeling of G} is called the full friendly index set of G, denoted by FFI（G）. In this paper, we will determine the full friendly index set of every Cartesian product of two cycles.

The Smallest Values of Algebraic Connectivity for Trees

The algebraic connectivity of a graph G is the second smallest eigenvalue of its Laplacian matrix. Let Fn be the set of all trees of order n. In this paper, we will provide the ordering of trees in 3n up to the last eight trees according to their smallest algebraic connectivities when n ≥ 13. This extends the result of Shao et al. [The ordering of trees and connected graphs by algebraic connectivity. Linear Algebra Appl., 428, 1421-1438 （2008）].

k-Factors in Regular Graphs

Plesnik in 1972 proved that an （m - 1）-edge connected m-regular graph of even order has a 1-factor containing any given edge and has another 1-factor excluding any given m - 1 edges. Alder et al. in 1999 showed that if G is a regular （2n ＋ 1）-edge-connected bipartite graph, then G has a 1-factor containing any given edge and excluding any given matching of size n. In this paper we obtain some sufficient conditions related to the edge-connectivity for an n-regular graph to have a k-factor containing a set of edges and （or） excluding a set of edges, where 1 ≤ k ≤n/2. In particular, we generalize Plesnik＇s result and the results obtained by Liu et al. in 1998, and improve Katerinis＇ result obtained 1993. Furthermore, we show that the results in this paper are the best possible.

Distance signless Laplacian spectrum of a graph

Let G be a simple connected graph with n vertices.The transmission Tv of a vertex v is defined to be the sum of the distances from v to all other vertices in G,that is,T_(v)=Σ_(u)∈Vd_(uv),where duv denotes the distance between u and v.Let T_(1),…,T_(n)be the transmission sequence of G.Let D=(dij)_(n×n)be the distance matrix of G,and T be the transmission diagonal matrix diag(T_(1),…,T_(n)).The matrix Q(G)=T+D is called the distance signless Laplacian of G.In this paper,we provide the distance signless Laplacian spectrum of complete k-partite graph,and give some sharp lower and upper bounds on the distance signless Laplacian spectral radius q(G).