具有匹配对网络模型的优美性

在当今网络研究中,人们需要将某些特殊的图分解为指定的结构.优美图可以被运用到图分解中.得到一些构造优美图的可算法化的方法,并构造较为复杂的优美图.     

一类偶阶图的边优美性

本文讨论了一类偶阶图的边优美性。同时得到了完全图是边优美图的充要条件。     

关于轮图优美标号的性质

设G=(V(G)),E(G))为p个顶点,q条边的连通简单图,以x和y为端点的边记作(x,y).定义1 称l为G的一个优美标号,如果l是一个单射:l:V(G)→{0,1,…,q}使得对所有边(x,y)∈E(G),由(?)(x,y)=|l(x)-l(y)|所定义的函数是一个—一对应.并称l(x)为顶点x的优美值.     

几类有趣图的奇优美性和奇强协调性

对于简单图G=〈V,E〉,如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1}满足:1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);2)max{f(v)|v∈V}=2|E|-1;3)对任意的e_1,e_2∈E,若e_1≠e_2,则g(e_1)≠g(e_2),此处g(e)=|f(u)+f(v)|,e=uv;4)|g(e)|e∈E}={1,3,5,…,2|E|-1},则称G为奇优美图,f称为G的奇优美标号.设G=〈V,E〉是一个无向简单图.如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1},满足:1)f是单射;2)■uv∈E(G),令f(uv)=f(u)+f(v),有{f(uv)|uv∈E(G)}={1,3,5,…,2|E|-1},则称G是奇强协调图,f称为G的.奇强协调标号或奇强协调值.给出了链图、升降梯等几类有趣图的奇优美标号和奇强协调标号.     

优美图的一些性质

对于一个(p,q)-图G,如果存在一个单射.f:V(G)→{0,1,…,q},使得边标号集合{f(uv)| uv∈E(G)}={1,2,…,q},其中边标号为f(uv)=|f(u)-f(v)|,那么称G是优美图,并称.f是G的一个优美标号.通过研究若干优美图,得出一些优美图的性质.     

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

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

灯笼图的奇优美标号

提出了灯笼图、多向灯笼图、复杂灯笼图,研究了它们的奇优美性,证明灯笼图是二分奇优美图、超级边魔幻图和超级反魔幻图.     

关于联图P_1VP_n的k-强优美性

本文研究了联图P_1VP_n的k-强优美性问题.利用K-强优美图的定义,获得了联图P_1VP_n是k-强优美图的必要条件,还得到了当n:2k-1时联图P_1VP_n是k-强优美图,亦是k-优美图,及当n≥3时联图P_1VP_n是2-强优美图,也是2-优美图的结果,推广了联图P_1VP_n是优美图的结果.     

关于p3n的优美性

设G(V,E)是一个简单图,对自然数k,当V(Gk)=V(G),E(Gk)=E(G)∪{uv|d(u,v)=k},则称图Gk为k-次方图.本文证明了图P3n的优美性.     

任意n个完备二分图的并图的k－优美性和算术性

证明了对于正整数k,n,si,ti（si,ti≥2,i=1,2,…,n）,图n/U/i=1,Ksi,ti是k-优美图;对于正整数k,d（d≥2）,k≠0（roodd）及n,si,ti（si,ti≥2,i=1,2,…,n）,图n/U/i=1,Ksi,ti是（k,d）-算术图,前一结论推广了文[6]的相应结果。     

若干并图的优美标号

证明了,对任意大于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)是优美图.     

Probabilistic Inductive Classes of Graphs

A unifying framework—probabilistic inductive classes of graphs (PICGs)—is defined by imposing a probability space on the rules and their left elements from the standard notion of inductive class of graphs. The rules can model the processes creating real-world social networks, such as spread of knowledge, dynamics of acquaintanceships or sexual contacts, and emergence of clusters. We demonstrate the characteristics of PICGs by casting some well-known models of growing networks in this framework. Results regarding expected size and order are derived. For PICG models of connected and 2-connected graphs order, size and asymptotic degree distribution are presented. The approaches used represent analytic alternative to computer simulation, which is mostly used to obtain the properties of evolving graphs.     

龙图的奇优美性

根据复杂网络研究的需要,定义(k,m)-奇优美龙图和一致(k,m)-龙图作为复杂网络的模型.这些龙图的奇优美性得到研究,其中证明方法可算法化.     

Bicolored Matchings in Some Classes of Graphs

We consider the problem of finding in a graph a set R of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with n nodes on each side, we give sufficient conditions for the existence of a set R with |R|=n+1 such that perfect matchings with k red edges exist for all k,0≤k≤n. Given two integers p<q we also determine the minimum cardinality of a set R of red edges such that there are perfect matchings with p red edges and with q red edges. For 3-regular bipartite graphs, we show that if p≤4 there is a set R with |R|=p for which perfect matchings M_k exist with |M_k∩R|≤k for all k≤p. For trees we design a linear time algorithm to determine a minimum set R of red edges such that there exist maximum matchings with k red edges for the largest possible number of values of k.     

具有较小直径的三类图的对极色数

对一个连通图G,令d(u,v)表示G中两个顶点间u和v之间的距离,d表示G的直径.G的一个对极染色指的是从G的顶点集到正整数集(颜色集)的一个映射c,使得对G的任意两个不同的顶点u和v满足d(u,v)+|c(u)-c(v)|≥d.由c映射到G的顶点的最大颜色称为c的值,记作ac(c),而对G的所有对极染色c,ac(c)的最小值称为G的对极色数,记作ac(G).本文确定了轮图、齿轮图以及双星图三类图的对极色数,这些图都具有较小的直径d.     

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.     

On Cyclic Decompositions of Complete Graphs into Tripartite Graphs

We introduce two new labelings for tripartite graphs and show that if a graph G with n edges admits either of these labelings, then there exists a cyclic G‐decomposition of for every positive integer x. We also show that if G is the union of two vertext‐disjoint cycles of odd length, other than , then G admits one of these labelings.     

Choosability with Separation of Complete Multipartite Graphs and Hypergraphs

For a hypergraph G and a positive integer s, let be the minimum value of l such that G is L‐colorable from every list L with for each and for all . This parameter was studied by Kratochvíl, Tuza, and Voigt for various kinds of graphs. Using randomized constructions we find the asymptotics of for balanced complete multipartite graphs and for complete k‐partite k‐uniform hypergraphs.