A lot of combinatorial objects have a natural bialgebra structure. In this paper, we prove that the vector space spanned by labeled simple graphs is a bialgebra with the conjunction product and the unshuffle coproduct...A lot of combinatorial objects have a natural bialgebra structure. In this paper, we prove that the vector space spanned by labeled simple graphs is a bialgebra with the conjunction product and the unshuffle coproduct. In fact, it is a Hopf algebra since it is graded connected. The main conclusions are that the vector space spanned by labeled simple graphs arising from the unshuffle coproduct is a Hopf algebra and that there is a Hopf homomorphism from permutations to label simple graphs.展开更多
A graph G is said to be one modulo N-difference mean graph if there is an injective function f from the vertex set of G to the set , where N is the natural number and q is the number of edges of G and f induces a bije...A graph G is said to be one modulo N-difference mean graph if there is an injective function f from the vertex set of G to the set , where N is the natural number and q is the number of edges of G and f induces a bijection from the edge set of G to given by and the function f is called a one modulo N-difference mean labeling of G. In this paper, we show that the graphs such as arbitrary union of paths, , ladder, slanting ladder, diamond snake, quadrilateral snake, alternately quadrilateral snake, , , , , friendship graph and admit one modulo N-difference mean labeling.展开更多
The cutwidth problem fora graph G is to embed G into a path such thatthe maximum number of overlap edges is minimized.This paperpresents an approach based on the degree se- quence of G for determining the exact valu...The cutwidth problem fora graph G is to embed G into a path such thatthe maximum number of overlap edges is minimized.This paperpresents an approach based on the degree se- quence of G for determining the exact value of cutwidth of typical graphs (e.g.,n- cube,cater- pillars) .Relations between the cutwidth and other graph- theoretic parameters are studied as wel展开更多
Let G be a simple graph. The cyclic bandwidth sum problem is to determine a labeling of graph G in a cycle such that the total length of edges is as small as possible. In this paper, some upper and lower bound...Let G be a simple graph. The cyclic bandwidth sum problem is to determine a labeling of graph G in a cycle such that the total length of edges is as small as possible. In this paper, some upper and lower bounds on cyclic bandwidth sum of graphs are studied.展开更多
<span style="font-family:Verdana;">This note is considered as a sequel of Yeh [<a href="#ref1">1</a>]. Here, we present a generalized (vertex) distance labeling (labeling vertices...<span style="font-family:Verdana;">This note is considered as a sequel of Yeh [<a href="#ref1">1</a>]. Here, we present a generalized (vertex) distance labeling (labeling vertices under constraints depending the on distance between vertices) of a graph. Instead of assigning a number (label) to each vertex, we assign a set of numbers to each vertex under given conditions. Some basic results are given in the first part of the note. Then we study a particular class of this type of labelings on several classes of graphs.</span>展开更多
A labeled graph is an ordered pair （G, L） consisting of a graph G and its labeling L ： V（G） → {1,2 ,n}, where n = ｜V（G）｜. An increasing nonconsecutive path in a labeled graph （G,L） is either a path （u1,u2...A labeled graph is an ordered pair （G, L） consisting of a graph G and its labeling L ： V（G） → {1,2 ,n}, where n = ｜V（G）｜. An increasing nonconsecutive path in a labeled graph （G,L） is either a path （u1,u2 uk） （k ≥ 2） in G such that L（u,） ＋ 2 ≤ L（ui＋1） for all i = 1, 2, ..., k- 1 or a path of order 1. The total number of increasing nonconsecutive paths in （G, L） is denoted by d（G, L）. A labeling L is optimal if the labeling L produces the largest d（G, L）. In this paper, a method simpler than that in Zverovich （2004） to obtain the optimal labeling of path is given. The optimal labeling of other special graphs such as cycles and stars is obtained.展开更多
The problem studied in this paper is to determine E(p,C),the maximum size of a connected graph G with the given vertex number p and cutwidth C. This paper presents some results on this problem.
Let G=(V,E)be a graph.For a vertex labeling f:V→Z2,it induces an edge labeling f+:E→Z2,where for each edge v1 v2∈E we have f+(v1 v2)=f(v1)+f(v2).For each i∈Z2,we use vf(i)(respectively,ef(i))to denote the number o...Let G=(V,E)be a graph.For a vertex labeling f:V→Z2,it induces an edge labeling f+:E→Z2,where for each edge v1 v2∈E we have f+(v1 v2)=f(v1)+f(v2).For each i∈Z2,we use vf(i)(respectively,ef(i))to denote the number of vertices(respectively,edges)with label i.A vertex labeling f of G is said to be friendly if vertices with different labels differ in size by at most one.The full friendly index set of a graph G,denoted by F F I(G),consists of all possible values of ef(1)-ef(0),where f ranges over all friendly labelings of G.In this paper,motivated by a problem raised by[6],we study the full friendly index sets of a family of cubic graphs.展开更多
The interval graph completion problem on a graph G is to find an added edge set F such that G + F is an interval supergraph with the smallest possible number of edges. The problem has important applications to numeric...The interval graph completion problem on a graph G is to find an added edge set F such that G + F is an interval supergraph with the smallest possible number of edges. The problem has important applications to numerical algebra, V LSI-layout and algorithm graph theory etc; And it has been known to be N P-complete on general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the interval graph completion problem on split graphs is investigated.展开更多
For a graph, a function is called an edge product cordial labeling of G, if the induced vertex labeling function is defined by the product of the labels of the incident edges as such that the number of edges with labe...For a graph, a function is called an edge product cordial labeling of G, if the induced vertex labeling function is defined by the product of the labels of the incident edges as such that the number of edges with label 1 and the number of edges with label 0 differ by at most 1 and the number of vertices with label 1 and the number of vertices with label 0 differ by at most 1. In this paper, we show that the graphs obtained by duplication of a vertex, duplication of a vertex by an edge or duplication of an edge by a vertex in a crown graph are edge product cordial. Moreover, we show that the graph obtained by duplication of each of the vertices of degree three by an edge in a gear graph is edge product cordial. We also show that the graph obtained by duplication of each of the pendent vertices by a new vertex in a helm graph is edge product cordial.展开更多
For a graph having no isolated vertex, a function is called an edge product cordial labeling of graph G, if the induced vertex labeling function defined by the product of labels of incident edges to each vertex is suc...For a graph having no isolated vertex, a function is called an edge product cordial labeling of graph G, if the induced vertex labeling function defined by the product of labels of incident edges to each vertex is such that the number of edges with label 0 and the number of edges with label 1 differ by at most 1 and the number of vertices with label 0 and the number of vertices with label 1 also differ by at most 1. In this paper, we discuss edge product cordial labeling for some cycle related graphs.展开更多
The cutwidth problem for a graph G is to embed G into a path P n such that the maximum number of overlap edges (i.e., the congestion) is minimized. It is known that the problem for general graphs is NP-hard while it ...The cutwidth problem for a graph G is to embed G into a path P n such that the maximum number of overlap edges (i.e., the congestion) is minimized. It is known that the problem for general graphs is NP-hard while it is polynomially solvable for trees. This paper presents an exact formula for the cutwidth of trees with diameter at most 4. A relation with the bandwidth is discussed as well.展开更多
The cutwidth of a graph G is the minimum number of overlap edges when G is embedded into a path Pn.The cutwidth problem for a graph G is to determine the cutwidth of G.A graph G with cutwidth k is k-cutwidth critical ...The cutwidth of a graph G is the minimum number of overlap edges when G is embedded into a path Pn.The cutwidth problem for a graph G is to determine the cutwidth of G.A graph G with cutwidth k is k-cutwidth critical if every proper subgraph of G has cutwidth less than k and G is homeomorphically minimal.In this paper,we completely investigated methods of forming a k-cutwidth(k>1)critical tree T.展开更多
Let k ? 2, 1 ? i ? k and α ? 1 be three integers. For any multiset which consists of some k-long oligonucleotides, a DNA labelled graph is defined as follows: each oligonucleotide from the multiset becomes a point; t...Let k ? 2, 1 ? i ? k and α ? 1 be three integers. For any multiset which consists of some k-long oligonucleotides, a DNA labelled graph is defined as follows: each oligonucleotide from the multiset becomes a point; two points are connected by an arc from the first point to the second one if the i rightmost nucleotides of the first point overlap with the i leftmost nucleotides of the second one. We say that a directed graph D can be (k, i; α)-labelled if it is possible to assign a label (l 1(x), ..., l k (x)) to each point x of D such that l j (x) ? {0, ..., α ? 1} for any j ? {1, ..., k} and (x, y) ? E(D) if and only if (l k?i+1(x), ..., l k (x)) = (l 1(y), ..., l i (y)). By the biological background, a directed graph is a DNA labelled graph if there exist two integers k, i such that it is (k, i; 4)-labelled. In this paper, a detailed discussion of DNA labelled graphs is given. Firstly, we study the relationship between DNA labelled graphs and some existing directed graph classes. Secondly, it is shown that for any DNA labelled graph, there exists a positive integer i such that it is (2i, i; 4)-labelled. Furthermore, the smallest i is determined, and a polynomial-time algorithm is introduced to give a (2i, i; 4)-labelling for a given DNA labelled graph. Finally, a DNA algorithm is given to find all paths from one given point to another in a (2i, i; 4)-labelled directed graph.展开更多
An antimagic labeling of a graph withq edges is a bijection from the set of edges to the set of positive integers{1,2,...,q}such that all vertex weights are pairwise distinct,where the vertex weight of a vertex is the...An antimagic labeling of a graph withq edges is a bijection from the set of edges to the set of positive integers{1,2,...,q}such that all vertex weights are pairwise distinct,where the vertex weight of a vertex is the sum of the labels of all edges incident with that vertex.A graph is antimagic if it has an antimagic labeling.In this paper,we provide antimagic labelings for a family of generalized pyramid graphs.展开更多
A graph is introduced,which allows of a combinatorial interpretation of a discrete-timesemi-infinite Lotka-Volterra (dLV) equation.In particular,Hankel determinants used in a determinantsolution to the dLV equation ar...A graph is introduced,which allows of a combinatorial interpretation of a discrete-timesemi-infinite Lotka-Volterra (dLV) equation.In particular,Hankel determinants used in a determinantsolution to the dLV equation are evaluated,via the Gessel-Viennot method,in terms of non-intersectingsubgraphs.Further,the recurrence of the dLV equation describing its time-evolution is equivalentlyexpressed as a time-evolution of weight of specific subgraphs.展开更多
文摘A lot of combinatorial objects have a natural bialgebra structure. In this paper, we prove that the vector space spanned by labeled simple graphs is a bialgebra with the conjunction product and the unshuffle coproduct. In fact, it is a Hopf algebra since it is graded connected. The main conclusions are that the vector space spanned by labeled simple graphs arising from the unshuffle coproduct is a Hopf algebra and that there is a Hopf homomorphism from permutations to label simple graphs.
文摘A graph G is said to be one modulo N-difference mean graph if there is an injective function f from the vertex set of G to the set , where N is the natural number and q is the number of edges of G and f induces a bijection from the edge set of G to given by and the function f is called a one modulo N-difference mean labeling of G. In this paper, we show that the graphs such as arbitrary union of paths, , ladder, slanting ladder, diamond snake, quadrilateral snake, alternately quadrilateral snake, , , , , friendship graph and admit one modulo N-difference mean labeling.
基金Supported by the National Natural Science Foundation of China (1 0 0 71 0 76 )
文摘The cutwidth problem fora graph G is to embed G into a path such thatthe maximum number of overlap edges is minimized.This paperpresents an approach based on the degree se- quence of G for determining the exact value of cutwidth of typical graphs (e.g.,n- cube,cater- pillars) .Relations between the cutwidth and other graph- theoretic parameters are studied as wel
文摘Let G be a simple graph. The cyclic bandwidth sum problem is to determine a labeling of graph G in a cycle such that the total length of edges is as small as possible. In this paper, some upper and lower bounds on cyclic bandwidth sum of graphs are studied.
文摘<span style="font-family:Verdana;">This note is considered as a sequel of Yeh [<a href="#ref1">1</a>]. Here, we present a generalized (vertex) distance labeling (labeling vertices under constraints depending the on distance between vertices) of a graph. Instead of assigning a number (label) to each vertex, we assign a set of numbers to each vertex under given conditions. Some basic results are given in the first part of the note. Then we study a particular class of this type of labelings on several classes of graphs.</span>
基金Supported in part by the NNSF of China(10301010,60673048)Science and Technology Commission of Shanghai Municipality(04JC14031).
文摘A labeled graph is an ordered pair （G, L） consisting of a graph G and its labeling L ： V（G） → {1,2 ,n}, where n = ｜V（G）｜. An increasing nonconsecutive path in a labeled graph （G,L） is either a path （u1,u2 uk） （k ≥ 2） in G such that L（u,） ＋ 2 ≤ L（ui＋1） for all i = 1, 2, ..., k- 1 or a path of order 1. The total number of increasing nonconsecutive paths in （G, L） is denoted by d（G, L）. A labeling L is optimal if the labeling L produces the largest d（G, L）. In this paper, a method simpler than that in Zverovich （2004） to obtain the optimal labeling of path is given. The optimal labeling of other special graphs such as cycles and stars is obtained.
基金Supported by Natural Science Foundation of Zhejiang Province(1 0 2 0 5 5 )
文摘The problem studied in this paper is to determine E(p,C),the maximum size of a connected graph G with the given vertex number p and cutwidth C. This paper presents some results on this problem.
基金Supported by the Zhejiang Provincial Natural Science Foundation of China(102055)Supported by the NSF of China(10471131)Supported by the Foundation of Zhejiang Universities' Youth Teachers
文摘The problem studied in this paper is to determine e（p, C）, the minimum size of a connected graph G with given vertex number p and cut-width C.
基金Supported by the National Natural Science Foundation of China(Grant No.11801149)Doctoral Fund of Henan Polytechnic University(Grant No.B2018-55)。
文摘Let G=(V,E)be a graph.For a vertex labeling f:V→Z2,it induces an edge labeling f+:E→Z2,where for each edge v1 v2∈E we have f+(v1 v2)=f(v1)+f(v2).For each i∈Z2,we use vf(i)(respectively,ef(i))to denote the number of vertices(respectively,edges)with label i.A vertex labeling f of G is said to be friendly if vertices with different labels differ in size by at most one.The full friendly index set of a graph G,denoted by F F I(G),consists of all possible values of ef(1)-ef(0),where f ranges over all friendly labelings of G.In this paper,motivated by a problem raised by[6],we study the full friendly index sets of a family of cubic graphs.
基金Supported by the National Natural Science Foundation of China（11101383） Supported by the Natural Science Foundation of Henan Province（112300410047）
文摘The interval graph completion problem on a graph G is to find an added edge set F such that G + F is an interval supergraph with the smallest possible number of edges. The problem has important applications to numerical algebra, V LSI-layout and algorithm graph theory etc; And it has been known to be N P-complete on general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the interval graph completion problem on split graphs is investigated.
文摘For a graph, a function is called an edge product cordial labeling of G, if the induced vertex labeling function is defined by the product of the labels of the incident edges as such that the number of edges with label 1 and the number of edges with label 0 differ by at most 1 and the number of vertices with label 1 and the number of vertices with label 0 differ by at most 1. In this paper, we show that the graphs obtained by duplication of a vertex, duplication of a vertex by an edge or duplication of an edge by a vertex in a crown graph are edge product cordial. Moreover, we show that the graph obtained by duplication of each of the vertices of degree three by an edge in a gear graph is edge product cordial. We also show that the graph obtained by duplication of each of the pendent vertices by a new vertex in a helm graph is edge product cordial.
文摘For a graph having no isolated vertex, a function is called an edge product cordial labeling of graph G, if the induced vertex labeling function defined by the product of labels of incident edges to each vertex is such that the number of edges with label 0 and the number of edges with label 1 differ by at most 1 and the number of vertices with label 0 and the number of vertices with label 1 also differ by at most 1. In this paper, we discuss edge product cordial labeling for some cycle related graphs.
基金Supported by the National Natural Science Foundation of China( 1 0 0 71 0 76)
文摘The cutwidth problem for a graph G is to embed G into a path P n such that the maximum number of overlap edges (i.e., the congestion) is minimized. It is known that the problem for general graphs is NP-hard while it is polynomially solvable for trees. This paper presents an exact formula for the cutwidth of trees with diameter at most 4. A relation with the bandwidth is discussed as well.
基金Supported by Soft Science Foundation of Henan Province(Grant No.192400410212)the Science and Technology Key Project of Henan Province of China(Grant No.22210211008)。
文摘The cutwidth of a graph G is the minimum number of overlap edges when G is embedded into a path Pn.The cutwidth problem for a graph G is to determine the cutwidth of G.A graph G with cutwidth k is k-cutwidth critical if every proper subgraph of G has cutwidth less than k and G is homeomorphically minimal.In this paper,we completely investigated methods of forming a k-cutwidth(k>1)critical tree T.
基金the National Natural Science Foundation of China (Grant No. 10471081)
文摘Let k ? 2, 1 ? i ? k and α ? 1 be three integers. For any multiset which consists of some k-long oligonucleotides, a DNA labelled graph is defined as follows: each oligonucleotide from the multiset becomes a point; two points are connected by an arc from the first point to the second one if the i rightmost nucleotides of the first point overlap with the i leftmost nucleotides of the second one. We say that a directed graph D can be (k, i; α)-labelled if it is possible to assign a label (l 1(x), ..., l k (x)) to each point x of D such that l j (x) ? {0, ..., α ? 1} for any j ? {1, ..., k} and (x, y) ? E(D) if and only if (l k?i+1(x), ..., l k (x)) = (l 1(y), ..., l i (y)). By the biological background, a directed graph is a DNA labelled graph if there exist two integers k, i such that it is (k, i; 4)-labelled. In this paper, a detailed discussion of DNA labelled graphs is given. Firstly, we study the relationship between DNA labelled graphs and some existing directed graph classes. Secondly, it is shown that for any DNA labelled graph, there exists a positive integer i such that it is (2i, i; 4)-labelled. Furthermore, the smallest i is determined, and a polynomial-time algorithm is introduced to give a (2i, i; 4)-labelling for a given DNA labelled graph. Finally, a DNA algorithm is given to find all paths from one given point to another in a (2i, i; 4)-labelled directed graph.
文摘An antimagic labeling of a graph withq edges is a bijection from the set of edges to the set of positive integers{1,2,...,q}such that all vertex weights are pairwise distinct,where the vertex weight of a vertex is the sum of the labels of all edges incident with that vertex.A graph is antimagic if it has an antimagic labeling.In this paper,we provide antimagic labelings for a family of generalized pyramid graphs.
文摘A graph is introduced,which allows of a combinatorial interpretation of a discrete-timesemi-infinite Lotka-Volterra (dLV) equation.In particular,Hankel determinants used in a determinantsolution to the dLV equation are evaluated,via the Gessel-Viennot method,in terms of non-intersectingsubgraphs.Further,the recurrence of the dLV equation describing its time-evolution is equivalentlyexpressed as a time-evolution of weight of specific subgraphs.
