Geodetic Number and Geo-Chromatic Number of 2-Cartesian Product of Some Graphs

A set S ⊆ V (G) is called a geodetic set if every vertex of G lies on a shortest u-v path for some u, v ∈ S, the minimum cardinality among all geodetic sets is called geodetic number and is denoted by . A set C ⊆ V (G) is called a chromatic set if C contains all vertices of different colors in G, the minimum cardinality among all chromatic sets is called the chromatic number and is denoted by . A geo-chromatic set Sc ⊆ V (G) is both a geodetic set and a chromatic set. The geo-chromatic number of G is the minimum cardinality among all geo-chromatic sets of G. In this paper, we determine the geodetic number and the geo-chromatic number of 2-cartesian product of some standard graphs like complete graphs, cycles and paths.

The Path-Positive Property on the Products of Graphs

The products of graphs discussed in this paper are the following four kinds: the Cartesian product of graphs, the tensor product of graphs, the lexicographic product of graphs and the strong direct product of graphs. It is proved that:① If the graphs G 1 and G 2 are the connected graphs, then the Cartesian product, the lexicographic product and the strong direct product in the products of graphs, are the path positive graphs. ② If the tensor product is a path positive graph if and only if the graph G 1 and G 2 are the connected graphs, and the graph G 1 or G 2 has an odd cycle and max{ λ 1μ 1,λ nμ m}≥2 in which λ 1 and λ n [ or μ 1 and μ m] are maximum and minimum characteristic values of graph G 1 [ or G 2 ], respectively.

Circular L(j,k)-labeling numbers of trees and products of graphs

Let j, k and m be three positive integers, a circular m-L（j, k）-labeling of a graph G is a mapping f： V（G）→{0, 1, …, m-1}such that f（u）-f（v）m≥j if u and v are adjacent, and f（u）-f（v）m≥k if u and v are at distance two,where a-bm=min{a-b,m-a-b}. The minimum m such that there exists a circular m-L（j, k）-labeling of G is called the circular L（j, k）-labeling number of G and is denoted by σj, k（G）. For any two positive integers j and k with j≤k,the circular L（j, k）-labeling numbers of trees, the Cartesian product and the direct product of two complete graphs are determined.

Domination Number of Square of Cartesian Products of Cycles

A set ?is a dominating set of G if every vertex of ?is adjacent to at least one vertex of S. The cardinality of the smallest dominating set of G is called the domination number of G. The square G2 of a graph G is obtained from G by adding new edges between every two vertices having distance 2 in G. In this paper we study the domination number of square of graphs, find a bound for domination number of square of Cartesian product of cycles, and find the exact value for some of them.

On the Signed Domination Number of the Cartesian Product of Two Directed Cycles

Let D be a finite simple directed graph with vertex set V(D) and arc set A(D). A function ?is called a signed dominating function (SDF) if ?for each vertex . The weight ?of f is defined by . The signed domination number of a digraph D is . Let Cm × Cn denotes the cartesian product of directed cycles of length m and n. In this paper, we determine the exact values of gs(Cm × Cn) for m = 8, 9, 10 and arbitrary n. Also, we give the exact value of gs(Cm × Cn) when m, ?(mod 3) and bounds for otherwise.

两类乘积图的集边控制数

图的集边控制数是研究图的边控制集划分问题的重要参数。采用分类讨论的方法,研究两类乘积图的集边控制数,分别确定了强乘积图P_(m)■P_(n)(m≥2,n≥3)和笛卡尔乘积图P_(2)×C_(n)的集边控制数。

可交换图的一些注记

如果存在一种顶点标号,使得2个简单图的邻接矩阵可交换,则称2个简单图可交换。首先,从图的Perron向量、主特征值数量、正则性三方面给出了可交换图的必要条件。然后,借助矩阵的克罗内克积、图的笛卡尔积及循环矩阵,构造了新的可交换图。最后,将一个邻接矩阵表示为另一个特征值互异的邻接矩阵的矩阵多项式,给出了2种算法,并比较了二者的优劣。可交换图存在公共的特征向量,对图谱理论研究具有重要意义。

Graph Laplacian Matrix Learning from Smooth Time-Vertex Signal

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.

图的Cartesian积结构分析及其Hedetniemi染色猜想

利用Cartesian积等价地表示出极大扩容图的代数结构,对Hedetniemi染色猜想进行了研究.根据极大扩容图的代数结构性质及与原图的关系,证明了简单图的若干次扩容图满足Hedetniemi染色猜想,得到了对Hedetniemi染色猜想成立的无限类图.

正则图Cartesian积的线图的秩

设G是一个顶点为n,度为r的正则图,那么它的边为m=1/2 nr.G的线图是顶点为m,度为(2r-2),边为1/2nr(r-1)的正则图.本文研究两个正则图或强正则图的Cartesian积图的线图的秩,得到了许多结果,推广了G.J.Davis,G.S.Domke等人的结论.

完全正则三部图与二部图的笛卡尔积的亏格

设Km,m,m(m≥1)是一个完全正则三部图,G是一个围长大于4的二部图.当G的最大度不大于2m时,本文得到完全正则三部图Km,m,m与G的笛卡尔积的亏格.我们的结果推广了Bonnington和Pisanski关于Km,m,m与偶圈的笛卡尔积的亏格.此外,我们还得到了Km,m,m与一些非二部图的笛卡尔积的不可定向亏格.

仙人掌图和卡氏积图的连通包数

测地线的概念起源于几何学、拓扑学及函数分析中的凸集理论,它在选址问题、网络设计及控制理论等方面有重要意义。在图论中定义了凸性后,测地线问题及与之相关的测地数问题成为揭示图的结构性质的一个重要指标及参数。图的连通包数是定义在图中测地线上的一个参数。针对计算图的连通包数问题,本研究用组合分析法确定了仙人掌图C_(n)·C_(n)及卡氏积图P_(m)×K_(2)、P_(m)×C_(3)、P_(2)×C_(n)的连通包数,其中m≥2,n≥3,P_(m)是长度为m-1的路,C_(n)是长度为n的圈。

Cartesian积图的边泛圈性

网络中子图的可嵌入性是度量网络优劣的一个重要性能。圈作为网络拓扑中一类重要的子图,其可嵌入性可以通过泛圈性来度量。Cartesian积图是互联网络拓扑结构中一类非常重要的图类。设G是长为k1和k2的圈的Cartesian积图。利用Cartesian积图的顶点和边的传递性,证明了当k1≥3,k2≥3,G是边偶泛圈的;当k1,k2均为奇数时,G是(k1+k22)-边泛圈的。

On the 2-Domination Number of Complete Grid Graphs

A set D of vertices of a graph G = (V, E) is called k-dominating if every vertex v ∈V-D is adjacent to some k vertices of D. The k-domination number of a graph G, γk (G), is the order of a smallest k-dominating set of G. In this paper we calculate the k-domination number (for k = 2) of the product of two paths Pm × Pn for m = 1, 2, 3, 4, 5 and arbitrary n. These results were shown an error in the paper [1].

Zero-M-Cordial Labeling of Some Graphs

In this paper we prove that the complete bipartite graph kmn where m and n are even, join of two cycle graphs cn and cm where n + m ≡ 0 (mod 4), split graph of cn for even “n”, Kn × P2 where n is even are admits a Zero-M-Cordial labeling. Further we prove that Kn × P2Bn = K1,n × P2 of odd n admits a Zero-M-Cordial labeling.

On Signed Domination of Grid Graph

Let G(V, E) be a finite connected simple graph with vertex set V(G). A function is a signed dominating function f : V(G)→{−1,1} if for every vertex v ∈ V(G), the sum of closed neighborhood weights of v is greater or equal to 1. The signed domination number γs(G) of G is the minimum weight of a signed dominating function on G. In this paper, we calculate the signed domination numbers of the Cartesian product of two paths Pm and Pn for m = 6, 7 and arbitrary n.

On Locating Numbers of Graphs

Let G =( V,E) be a connected graph and W = { w_1,w_2,…,w_k} be an ordered subset of V( G).For any vertex v ∈V,the locating code of v with respect to W is the k-vector CW( v) = { d( v,w_1),d( v,w_2),…,d( v,w_k) },W is said to be a locating set of G if distinct vertices have the distinct locating code,and the locating number of G is defined as: Loc( G) = min{ | W| : W is a locating set of G}.We study the locating set and locating number of a graph G,obtain some bounds for the locating numbers of graphs,and determine the exact value of Loc( G) for some special classes of graphs,such as cycles,wheels,complete t-partite graph and some Cartesian products of paths and cycles. In addition,we also prove that Loc( T) ≥Δ-1 holds for all trees T with maximum degree Δ,and shows a tree T with Loc( T) = Δ-1.

SOME PROPERTIES OF A CLASS OF INTERCHANGE GRAPHS

Abstract Let U(R,S) denote the class of all (0,1) m×n matrices having row sum vector R and column sum vector S. The interchange graph G(R,S) is the graph where the vertices are the matrices in U(R,S) and two vertices representing two such matrices are adjacent provided they differ by an interchange. It is proved that G(R,(1,1,...,1)) is a generalized Cartesian product of some Johnson Scheme graphs. Furthermore, its connectivity, diameter and transitivity (vertex ,edge ) are also determined.

笛卡儿积图的2-hued列表染色

给定图G的一个列表分配L,图G的一个(L,r)-染色,是一个正常染色c满足:每个顶点v都至少和min{d(v),r}种不同颜色的顶点相邻,并且c(v)属于L(v).图G的r-hued列表染色数,记为χL,r(G),是最小正整数k满足对于任意一个|L(v)|=k的列表分配L,图G有一个(L,r)-染色.最后证明了χL,2(P_(m)□P_(n))=4,并且确定了χL,2(P_(m)□C_(n))的范围.

K_(n)□K_(m,s)的r-hued染色

考虑完全图K_(n)和完全二部图K_(m,s)的笛卡尔乘积图的r-hued色数.首先,根据正整数r的不同值进行分类,并结合K_(n)□K_(m,s)的性质,刻画该图r-hued色数的下界;其次,找到K_(n)□K_(m,s)的一个具体的(k,r)-染色,并以此刻画该图r-hued色数的一个上界;最后,确定了K_(n)□K_(m,s)的r-hued色数.