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 supe...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.展开更多
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 di...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.展开更多
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...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 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)...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展开更多
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 e...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)].展开更多
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...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.展开更多
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 dista...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).展开更多
基金Partially supported by Faculty-Research Grant,Hong Kong Baptist University
文摘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.
基金Supported by Faculty Research Grant, Hong Kong Baptist University
文摘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.
基金Supported by FRG/07-08/II-08 Hong Kong Baptist University
文摘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.
基金Supported by FRG, Hong Kong Baptist-University the first author is supported by National Natural Science Foundation of China (Grant No. 10671061) The authors would like to thank the anonymous referee for a number of helpful suggestions.
文摘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
基金Supported by FRG, Hong Kong Baptist University, National Science Foundation (NSF) of China (Grant Nos.10871204, 11101358)NSF of Fujian (Grant Nos. 2011J05014, 2011J01026)+2 种基金Project of Fujian Education Department (Grant No. JA11165)Fundamental Research Funds for the Central Universities (Grant No. 09CX04003A)Research Fund of Zhangzhou Normal University (Grant No. SJ1004)
文摘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)].
基金FRGHong Kong Baptist University NSFC (60673047)SRFDP (20040422004) of China
文摘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.
基金supported by the National Natural Science Foundation of China(Grant Nos.11801144,11701148)the Natural Science Foundation of Education Ministry of Henan Province(18B110005).
文摘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).