A strong product graph is denoted by G_(1)■G_(2),where G_(1) and G_(2) are called its factor graphs.This paper gives the range of the minimum strong radius of the strong product graph.And using the relationship betwe...A strong product graph is denoted by G_(1)■G_(2),where G_(1) and G_(2) are called its factor graphs.This paper gives the range of the minimum strong radius of the strong product graph.And using the relationship between the cartesian product graph G_(1)■G_(2) and the strong product graph G_(1)■G_(2),another different upper bound of the minimum strong radius of the strong product graph is given.展开更多
In this paper,we focus on inferring graph Laplacian matrix from the spatiotemporal signal which is defined as“time-vertex signal”.To realize this,we first represent the signals on a joint graph which is the Cartesia...In this paper,we focus on inferring graph Laplacian matrix from the spatiotemporal signal which is defined as“time-vertex signal”.To realize this,we first represent the signals on a joint graph which is the Cartesian product graph of the time-and vertex-graphs.By assuming the signals follow a Gaussian prior distribution on the joint graph,a meaningful representation that promotes the smoothness property of the joint graph signal is derived.Furthermore,by decoupling the joint graph,the graph learning framework is formulated as a joint optimization problem which includes signal denoising,timeand vertex-graphs learning together.Specifically,two algorithms are proposed to solve the optimization problem,where the discrete second-order difference operator with reversed sign(DSODO)in the time domain is used as the time-graph Laplacian operator to recover the signal and infer a vertex-graph in the first algorithm,and the time-graph,as well as the vertex-graph,is estimated by the other algorithm.Experiments on both synthetic and real-world datasets demonstrate that the proposed algorithms can effectively infer meaningful time-and vertex-graphs from noisy and incomplete data.展开更多
In this paper, we propose a new perspective to discuss the N-order fixed point theory of set-valued and single-valued mappings. There are two aspects in our work: we first define a product metric space with a graph fo...In this paper, we propose a new perspective to discuss the N-order fixed point theory of set-valued and single-valued mappings. There are two aspects in our work: we first define a product metric space with a graph for the single-valued mapping whose conversion makes the results and proofs concise and straightforward, and then we propose an <em>SG</em>-contraction definition for set-valued mapping which is more general than some recent contraction’s definition. The results obtained in this paper extend and unify some recent results of other authors. Our method to discuss the N-order fixed point unifies <em>N</em>-order fixed point theory of set-valued and single-valued mappings.展开更多
An L(2, 1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x) - f(y)| 〉 2 if d(x, y) = 1 and |f(x)-f(y)| ≥ 1 ifd(x, y) = 2. The ...An L(2, 1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x) - f(y)| 〉 2 if d(x, y) = 1 and |f(x)-f(y)| ≥ 1 ifd(x, y) = 2. The L(2, 1)-labeling number λ(G) of G is the smallest number k such that G has an L(2, 1)-labeling with max{f(v) : v ∈ V(G)} = k. We study the L(3, 2, 1)-labeling which is a generalization of the L(2, 1)-labeling on the graph formed by the (Cartesian) product and composition of 3 graphs and derive the upper bounds of λ3(G) of the graph.展开更多
The star chromatic number of a graph was introduced by A. Vince, which is a natural generalization of the chromatic number of a graph. In this paper, the star chromatic numbers of graph products GH are discussed in so...The star chromatic number of a graph was introduced by A. Vince, which is a natural generalization of the chromatic number of a graph. In this paper, the star chromatic numbers of graph products GH are discussed in some special cases.展开更多
An independent set in a graph G is a set of pairwise non-adjacent vertices.Let ik(G)denote the number of independent sets of cardinality k in G.Then its generating function I(G;x)=∑^(α(G))^(k=0)ik(G)x^(k),is called ...An independent set in a graph G is a set of pairwise non-adjacent vertices.Let ik(G)denote the number of independent sets of cardinality k in G.Then its generating function I(G;x)=∑^(α(G))^(k=0)ik(G)x^(k),is called the independence polynomial of G(Gutman and Harary,1983).In this paper,we introduce a new graph operation called the cycle cover product and formulate its independence polynomial.We also give a criterion for formulating the independence polynomial of a graph.Based on the exact formulas,we prove some results on symmetry,unimodality,reality of zeros of independence polynomials of some graphs.As applications,we give some new constructions for graphs having symmetric and unimodal independence polynomials.展开更多
It is proved that if G is a (+1)-colorable graph, so are the graphs G×Pn and C×Cn, where Pn and Cn are respectively the path and cycle with n vertices, and the maximum edge degree of the graph. The exact ch...It is proved that if G is a (+1)-colorable graph, so are the graphs G×Pn and C×Cn, where Pn and Cn are respectively the path and cycle with n vertices, and the maximum edge degree of the graph. The exact chromatic numbers of the product graphs and are also presented. Thus the total coloring conjecture is proved to be true for many other graphs.展开更多
基金Supported by National Natural Science Foundation of China(Grant No.11551002)Natural Science Foundation of Qinghai Province(Grant No.2019-ZJ-7093)。
文摘A strong product graph is denoted by G_(1)■G_(2),where G_(1) and G_(2) are called its factor graphs.This paper gives the range of the minimum strong radius of the strong product graph.And using the relationship between the cartesian product graph G_(1)■G_(2) and the strong product graph G_(1)■G_(2),another different upper bound of the minimum strong radius of the strong product graph is given.
基金supported by the National Natural Science Foundation of China(Grant No.61966007)Key Laboratory of Cognitive Radio and Information Processing,Ministry of Education(No.CRKL180106,No.CRKL180201)+1 种基金Guangxi Key Laboratory of Wireless Wideband Communication and Signal Processing,Guilin University of Electronic Technology(No.GXKL06180107,No.GXKL06190117)Guangxi Colleges and Universities Key Laboratory of Satellite Navigation and Position Sensing.
文摘In this paper,we focus on inferring graph Laplacian matrix from the spatiotemporal signal which is defined as“time-vertex signal”.To realize this,we first represent the signals on a joint graph which is the Cartesian product graph of the time-and vertex-graphs.By assuming the signals follow a Gaussian prior distribution on the joint graph,a meaningful representation that promotes the smoothness property of the joint graph signal is derived.Furthermore,by decoupling the joint graph,the graph learning framework is formulated as a joint optimization problem which includes signal denoising,timeand vertex-graphs learning together.Specifically,two algorithms are proposed to solve the optimization problem,where the discrete second-order difference operator with reversed sign(DSODO)in the time domain is used as the time-graph Laplacian operator to recover the signal and infer a vertex-graph in the first algorithm,and the time-graph,as well as the vertex-graph,is estimated by the other algorithm.Experiments on both synthetic and real-world datasets demonstrate that the proposed algorithms can effectively infer meaningful time-and vertex-graphs from noisy and incomplete data.
文摘In this paper, we propose a new perspective to discuss the N-order fixed point theory of set-valued and single-valued mappings. There are two aspects in our work: we first define a product metric space with a graph for the single-valued mapping whose conversion makes the results and proofs concise and straightforward, and then we propose an <em>SG</em>-contraction definition for set-valued mapping which is more general than some recent contraction’s definition. The results obtained in this paper extend and unify some recent results of other authors. Our method to discuss the N-order fixed point unifies <em>N</em>-order fixed point theory of set-valued and single-valued mappings.
文摘An L(2, 1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x) - f(y)| 〉 2 if d(x, y) = 1 and |f(x)-f(y)| ≥ 1 ifd(x, y) = 2. The L(2, 1)-labeling number λ(G) of G is the smallest number k such that G has an L(2, 1)-labeling with max{f(v) : v ∈ V(G)} = k. We study the L(3, 2, 1)-labeling which is a generalization of the L(2, 1)-labeling on the graph formed by the (Cartesian) product and composition of 3 graphs and derive the upper bounds of λ3(G) of the graph.
文摘The star chromatic number of a graph was introduced by A. Vince, which is a natural generalization of the chromatic number of a graph. In this paper, the star chromatic numbers of graph products GH are discussed in some special cases.
基金Supported by National Natural Science Foundation of China(Grant Nos.11971206,12022105)Natural Science Foundation for Distinguished Young Scholars of Jiangsu Province(Grant No.BK20200048)。
文摘An independent set in a graph G is a set of pairwise non-adjacent vertices.Let ik(G)denote the number of independent sets of cardinality k in G.Then its generating function I(G;x)=∑^(α(G))^(k=0)ik(G)x^(k),is called the independence polynomial of G(Gutman and Harary,1983).In this paper,we introduce a new graph operation called the cycle cover product and formulate its independence polynomial.We also give a criterion for formulating the independence polynomial of a graph.Based on the exact formulas,we prove some results on symmetry,unimodality,reality of zeros of independence polynomials of some graphs.As applications,we give some new constructions for graphs having symmetric and unimodal independence polynomials.
基金Project supported by National Natural Science Foundation(No. 69882002) and "973" project (No. G1999035805)
文摘It is proved that if G is a (+1)-colorable graph, so are the graphs G×Pn and C×Cn, where Pn and Cn are respectively the path and cycle with n vertices, and the maximum edge degree of the graph. The exact chromatic numbers of the product graphs and are also presented. Thus the total coloring conjecture is proved to be true for many other graphs.