反超图的笛卡儿积的上色数

讨论反超图的笛卡儿积的着色理论 ,求出了满足一定条件的反超图的笛卡儿积的上色数 .     

广义字典序积的自同态幺半群

讨论了图的广义字典序积的自同态幺半群的性质,给出了广义字典序积图X[Yz|x∈V（X）]的自同态幺半群与X,Yx(x∈V(X))的自同态幺半群的圈积相等的充要条件。     

集合笛卡儿积集中文氏图的一种推广

介绍了涉及集合笛卡儿积(Cartesian product)的运算性质讨论的一种类似于文氏图(Venn diagram)的方法.     

图的笛卡儿积的测地数

对于图G内的任意两点u和v，u-v测地线是指u和v之间的最短路．I（u，v）表示位于u-v测地线上所有点的集合，对于．S∈V（G），I（S）表示所有I（u，v）的并，这里“u,v∈．S．G的测地数g（G）是使I（S）=V（G）的点集．S的最小基数．在这篇文章，我们研究G×K3的测地数和g（G）与g（G×K3）相等的充分必要条件，还给出了T×Km和Cn×Km的测地数，这里T是树．     

$W_m$与$P_n$ 的笛卡儿积图的交叉数

Most results on crossing numbers of graphs focus on some special graphs, such as the Cartesian products of small graphs with path, star and cycle. In this paper, we obtain the crossing number formula of Cartesian products of wheel Wm with path Pn, for arbitrary m ≥ 3 and n≥ 1.     

一些条件连通图的关系

在这篇文章中，我们主要研究一些条件连通图之间的关系，如上连通，上边连通，超连通和上混合连通．     

树的笛卡儿积的测地数

图G内的任意两点u和υ,u-υ测地线是指u和υ之间的最短路.I(u,υ)表示位于u一υ测地线上所有点的集合,对于子集S∈V(G),I(s)表示所有,(u,υ)的并,这里u,υ∈S.图G的测地数g(G)是使,I(s):V(G)的点集S的最小基数.本文研究了任意连通图G与树T笛卡儿积的测地数的界,同时,给出了任意两个树T1与T2笛卡儿积的测地数和树T与圈C笛卡儿积的测地数.     

图的字典序积和自同态幺半群

Ｆ．Ｈａｒａｒｙ￣［１］和Ｇ．Ｓａｂｉｄｕｓｓｉ￣［２］考虑过图Ｘ和ｙ的字典序积Ｘ［Ｙ］的自同构群ＡｕｔＸ［Ｙ］与它们各自的自同构群的圈积ＡｕｔＸ［ＡｕｔＹ］的关系，并给出了两者相等的一种刻划．在本文，我们考虑更广意义上的问题，即Ｘ［Ｙ］的自同态幺半群ＥｎｄＸ［Ｙ］与各自的自同态幺半群的圈积ＥｎｄＸ［ＥｎｄＹ］的关系，也给出了两者相等的一种刻划，同时得到了下面结果：如果Ｘ和Ｙ都是不含Ｋ＿３导出子图的连通图，且其中之一图有奇数围长，那么ＥｎｄＸ［Ｙ］＝ＥｎｄＸ［ＥｎｄＹ］．     

太阳图与路的笛卡儿积图的任意可分性（英文）

一个阶为n的图G称为是任意可分的(简作AP),如果对于任一正整数序列τ=(n₁,n₂,…,n_k)满足n=n₁+n₂+…+n_k,总是存在顶点集V(G)的一个划分(V₁,V₂,…,V_k)满足:对于i∈[1,k],|V_i|=n_i,且子图G|V_i|是图G的V_i导出的一个连通子图.我们用S~*=S(n;m₁,m₂,…,m_n)来表示最大度△(S~*)=3的太阳图.本文讨论了图S~*P_m(m≥3)的任意可分性.     

图的字典积的非零整数流(英文)

充分利用图的字典积的结构证明了以下结论:如果图G_1的每连通分支都非平凡,图G_2的阶数大于3,那么它们的字典积G_1[G_2]具有非零3-流.     

笛卡尔乘积图的圈点连通度

图G的圈点连通度,记为κ_c(G),是所有圈点割中最小的数目,其中每个圈点割S满足G-S不连通且至少它的两个分支含圈.这篇文章中给出了两个连通图的笛卡尔乘积的圈点连通度:(1)如果G_1≌K_m且G_2≌K_n,则κ_c(G_1×G_2)=min{3m+n-6,m+3n-6},其中m+n≥8,m≥n+2,或n≥m+2,且κ_c(G_1×G_2)=2m+2n-8,其中m+n≥8,m=n,或n=m+1,或m=n+11;(2)如果G_1≌K_m(m≥3)且G_2■K_n,则min{3m+κ(G_2)-4,m+3κ(G_2)-3,2m+2κ(G_2)-4}≤κ_c(G_1×G_2)≤mκ(G2);(3)如果G_1■K_m,K_(1,m-1)且G_2■K_n,K_(1,n-1),其中m≥4,n≥4,则min{3κ(G_1)+κ(G_2)-1,κ(G_1)+3κ(G_2)-1,2_κ(G_1)+2_κ(G_2)-2}≤κ_c(G_1×G_2)≤min{mκ(G_2),nκ(G_1),2m+2n-8}.     

Treewidth of Cartesian Products of Highly Connected Graphs

The following theorem is proved: for all k‐connected graphs G and H each with at least n vertices, the treewidth of the cartesian product of G and H is at least . For , this lower bound is asymptotically tight for particular graphs G and H. This theorem generalizes a well‐known result about the treewidth of planar grid graphs.     

有向图字典乘积的代数群性质

字典乘积有向图G_1→⊙G_2是通过已知阶数较小的有向图G_1和G_2构造来的,这些小有向图G_1和G_2的拓扑结构和性质肯定影响大有向图G_1→⊙G_2的拓扑结构和性质.运用群论方法,证明了有向图字典乘积的一些代数性质,如:结合律、分配律等.     

交叉数为2且因子图为路的笛卡尔积图

M.Kle??和J.Petrillová刻画了当G1为圈且cr (G1G2)=2时,因子图G1和G2所满足的充要条件.在此基础上,该文进一步刻画了在cr (G1G2)=2的前提下,当G1=P4,或者G1=P3且△(G2)=4时,因子图G2应满足的充要条件.     

Affine Completeness and Lexicographic Product Decompositions of Abelian Lattice Ordered Groups

In this paper it is proved that an abelian lattice ordered group which can be expressed as a nontrivial lexicographic product is never affine complete. This work was supported by VEGA grant 2/1131/21.     

Characterizing Flag Graphs and Induced Subgraphs of Cartesian Product Graphs

The vertices of the flag graph Φ(P) of a graded poset P are its maximal chains. Two vertices are adjacent whenever two maximal chains differ in exactly one element. In this paper we characterize induced subgraphs of Cartesian product graphs and flag graphs of graded posets. The latter class of graphs lies between isometric and induced subgraphs of Cartesian products in the embedding structure theory. Both characterization use certain edge-labelings of graphs.     

Hadwiger Number and the Cartesian Product of Graphs

The Hadwiger number η(G) of a graph G is the largest integer n for which the complete graph K _n on n vertices is a minor of G. Hadwiger conjectured that for every graph G, η(G) ≥ χ(G), where χ(G) is the chromatic number of G. In this paper, we study the Hadwiger number of the Cartesian product of graphs. As the main result of this paper, we prove that for any two graphs G ₁ and G ₂ with η(G ₁) = h and η(G ₂) = l. We show that the above lower bound is asymptotically best possible when h ≥ l. This asymptotically settles a question of Z. Miller (1978). As consequences of our main result, we show the following: