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

本文所讨论的积图是图的笛卡尔积，图的张量积，图的逻辑积和图的强直积四种积图．证明了：①如果Ｇ１和Ｇ２都是连通图，则积图中笛卡尔积，逻辑积和强直积都是道路正图．②图的张量积是道路正图的是图Ｇ１和Ｇ２是一个连通图，Ｇ１［或Ｇ２］有一个奇圈，且ｍａｘ｛λ１μ１，λｎμｍ｝≥２。

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.

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.

可交换图的一些注记

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

图的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等人的结论.

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色数.

带故障边的路和圈的笛卡尔乘积图的哈密尔顿路

容错哈密尔顿性是互连网络研究的经典问题之一,它是衡量一个网络可靠性的重要标准,被广泛应用到当前大型分布式系统的网络拓扑中。该文研究具有一条故障边的路和圈的笛卡尔乘积图P_(m)×C_(n)上的哈密尔顿路存在问题,根据故障边位置的不同,对当m≥3,n≥5且n是奇数时的P_(m)×C_(n)中哈密尔顿路进行了刻画。

The Crossing Numbers of Cartesian-Products of Stars and 5-Vertex Graphs

In this paper, the crossing numbers of the Cartesian products of a specific 5-vertex graph with a star are given, and thus the result fills up the crossing number list of Cartesian products of all 5-vertex graphs with stars （presented by Marian Klesc）. In addition, we also give an up to date description of Cartesian products of 5-vertex graphs with stars, whose crossing numbers are known.

关于C_m×C_(5n)的全色数和邻强边色数

设G是一个简单图,k为正整数,V(G)∪E(G)到{1,2,…,k}的一个映射f满足:对于任意的uv∈E(G)有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);任意的uv,vw∈E(G),u≠w,有f(uv)≠f(uw),则称f为G的k-全染色,简记为k-TC,并称ΧT(G)=min{k|G存在k-TC}为G的全色数.证明了圈Cm与圈C5n的笛卡尔积图的全色数和邻强边色数都为5.

若干图类的邻强边染色

研究了若干图类的邻强边染色 .利用在图中添加辅助点和边的方法 ,构造性的证明了对于完全图 Kn和路 Lm 的笛卡尔积图 Kn× Lm,有χ′as(Kn× Lm) =△ (Kn× Lm) +1 ,其中△ (Kn× Lm)和χ′as(Kn× Lm)分别表示图 Kn× Lm的最大度和邻强边色数 .同理验证了 n阶完全图 Kn的广义图 K(n,m)满足邻强边染色猜想 .