图Km,n∪Kp,q的k优美性

路线等在[3]中证明了当k>1,且min{p,q}≥2时,图St(m)∪Kp,q是k优美图.本文论证了当min{m,n,p,q}≥2时,图Km,n∪Kp,q是k优美图.     

关于偶图的K—优美性

本文引进了图G(G_1,G_2,…,G_(|E(G)|))、G(G_1~(|E(G)|))的概念,此外,还引进了序优美图、可逆优美图、偶图的优美函数等概念,对于某些特殊的偶图,给出了利用小阶优美偶图构造大阶优美偶图的一种方法,由此证明了某些偶图是K-优美图。     

若干并图的优美标号

证明了,对任意大于1的自然数m,n,p,非连通图(■ V ■)∪K_(n,p)是优美图;当k≤p,m=kn+3或m=kn+1时,非连通图(P_2 V ■)∪K_(n,p)是优美图;当p≥2,m=3k+1时,非连通图(P_2 V ■)∪K_(3,p)是优美图;对任意正整数n,p,非连通图(P_1 V P_(2n+2))∪_(n,p)是优美图.     

关于图B（m,n,p）的优美性

在［１］［２］中已证明“除去三种特殊情形，连结两个顶点的三条独立路所成简单图Ｂ（ｍ，ｎ，ｐ）是优美图”，并猜想：对除去的三种情形，Ｂ（ｍ，ｎ，ｐ）也是优美的。本文证实了上术猜想。这样一来，也就证明了［３］中的猜想：有－ｈ－链弦的圈是优美的（ｈ≥２）。     

关于图P3n优美性的研究

在n个顶点的路Pn上,当且仅当两点的距离为3时增加一条边,所得的图称为P3n,本文给出了图P3n(n≥4)的优美标号,从而证明了P3n都是优美图.     

关于笛卡尔乘积图的优美性

研究了笛卡尔乘积图Pm×Pn×P1的优美标号算法,并且给出了他们都是优美图的证明,同时推广了笛卡尔乘积图Pm×Pn是优美图的结论.     

关于P（n1,n2,...nm）和Dm,4的优美性

一个简单图G=(V,E)是k-优美的(k≥1的整数),如果存在一个1-1映射 f:V(G)→(0,1,…,|E| k-1)使得对所有的边e=wv∈E(G),由f~*(u,v)=|f(u)-f(v)|导出的映射 E(G)→{k,k 1,…,|E| k-1}是一个1-1对应。这个关于k-优美的概念是由Slater和Thuillier相互独立地提出来的。当k=1,就是我们通常研究的优美图。显然,k-优美图一定是1-优美图。反之不真。例如,三回路c_3是1-优美图,但对k>1,非k-优美。     

一类图优美性的证明

本文给出一种 GL 阵的概念,把若干 GL 阵进行各种运算,所得的 GL 阵对应的图是优美的。从而得到为数众多的一类图,如放射树等,都是优美图。在[2][3]和[4]中,利用 GL 阵还证明了优美图 Bodendiek 猜想及其一种推广。     

由圈得到的一类优美图

本文证明了ｎ个顶点的圈增加若干条弦所得到的图优美．     

图^nUi=1 Fmi,t和^nUi=1 Hmi,t的优美性

本文构造了两类非连通图^nUi=1 Fmi,t和^nUi=1 Hmi,t并证明了这两类图是优美的，且也是交错的。     

Decomposition of Complete Graphs into Isomorphic Complete Bipartite Graphs

A decomposition of a complete graph into disjoint copies of a complete bipartite graph is called a ‐design of order n. The existence problem of ‐designs has been completely solved for the graphs for , for , K_{2, 3} and K_{3, 3}. In this paper, I prove that for all , if there exists a ‐design of order N, then there exists a ‐design of order n for all (mod ) and . Giving necessary direct constructions, I provide an almost complete solution for the existence problem for complete bipartite graphs with fewer than 18 edges, leaving five orders in total unsolved.     

Unbalanced Star-Factorizations of Complete Bipartite Graphs II

There are simple arithmetic conditions necessary for the complete bipartite graph K_m,n to have a complete factorization by subgraphs which are made up of disjoint copies of K_p,q. It is conjectured that these conditions are also sufficient. In any factor the copies of K_p,q have two orientations depending which side of the bipartition the p-set lies. The balance ratio is the relative proportion, x:y of these where gcd(x,y)=1. In this paper, we continue the study of the unbalanced case (y > x) where p = 1, to show that the conjecture is true whenever y is sufficiently large. We also prove the conjecture for K_1,4-factorizations.     

Decomposition of Complete Bipartite Even Graphs into Closed Trails

We prove that any complete bipartite graph K _a,b , where a, b are even integers, can be decomposed into closed trails with prescribed even lengths.     

Remarks on Vertex-Distinguishing IE-Total Coloring of Complete Bipartite Graphs K4,n and Kn,n

Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color.Let C(u) be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)=C(v) for any two different vertices u and v of V(G),then f is called a k-vertex-distinguishing IE-total-coloring of G,or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by χ ie vt (G),and it is called the VDIET chromatic number of G.We will give VDIET chromatic numbers for complete bipartite graph K4,n (n≥4),K n,n (5≤ n ≤ 21) in this article.     

Chaotic Numbers of Complete Bipartite Graphs and Tripartite Graphs

In this paper, we study the chaotic numbers of complete bipartite graphs and complete tripartite graphs. For the complete bipartite graphs, we find closed-form formulas of the chaotic numbers and characterize all chaotic mappings. For the complete tripartite graphs, we develop an algorithm running in O(n ⁴ ₃) time to find the chaotic numbers, with n ₃ the number of vertices in the largest partite set.Research supported by NSC 90-2115-M-036-003.The author thanks the authors of Ref. 6, since his work was motivated by their work. Also, the author thanks the referees for helpful comments which made the paper more readable.     

Vertex-distinguishing IE-total Colorings of Complete Bipartite Graphs K8,n

Let G be a simple graph. An IE-total coloring f of G is a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color. For each vertex x of G, let C(x) be the set of colors of vertex x and edges incident to x under f. For an IE-total coloring f of G using k colors, if C(u) 6= C(v) for any two different vertices u and v of G, then f is called a k-vertex-distinguishing IE-total-coloring of G or a k-VDIET coloring of G for short. The minimum number of colors required for a VDIET coloring of G is denoted by χievt(G) and is called vertex-distinguishing IE-total chromatic number or the VDIET chromatic number of G for short. The VDIET colorings of complete bipartite graphs K8,n are discussed in this paper. Particularly, the VDIET chromatic number of K8,n are obtained.     

有关完全图的图的紧性

双随机矩阵有许多重要的应用,紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,具有重要的研究价值.确定一个图是否紧图是个困难的问题,目前已知的紧图族尚且不多,给出了三个结果:任意多个完全图的不交并是紧图;圈C_3与圈C_n(n3)的不交并是非紧图;当n是大于等于3的奇数时,完全图K_n与图K_(n+1)的不交并是非紧图,其中图K_(n+1)是从完全图K_(n+1)删去一因子而得到的图.     

Signed Roman (Total) Domination Numbers of Complete Bipartite Graphs and Wheels

A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for any v ∈ V, where N [v] is the closed neighborhood and N(v) is the neighborhood of v, and(ii) every vertex v for which f(v) =-1 is adjacent to a vertex u for which f(u) = 2. The weight of a SRDF(res. STRDF) is the sum of its function values over all vertices.The signed(res. signed total) Roman domination number of G is the minimum weight among all signed(res. signed total) Roman dominating functions of G. In this paper,we compute the exact values of the signed(res. signed total) Roman domination numbers of complete bipartite graphs and wheels.     

Interval Minors of Complete Bipartite Graphs

Interval minors of bipartite graphs were recently introduced by Jacob Fox in the study of Stanley–Wilf limits. We investigate the maximum number of edges in ‐interval minor‐free bipartite graphs. We determine exact values when and describe the extremal graphs. For , lower and upper bounds are given and the structure of ‐interval minor‐free graphs is studied.     

关于完全二部图$K_{4, n}$和$K_{n, n}$的点可区别 $IE$-全染色的一些注记

Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color.Let C(u) be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)=C(v) for any two different vertices u and v of V(G),then f is called a k-vertex-distinguishing IE-total-coloring of G,or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by χ ie vt (G),and it is called the VDIET chromatic number of G.We will give VDIET chromatic numbers for complete bipartite graph K4,n (n≥4),K n,n (5≤ n ≤ 21) in this article.