复合图的1－因子分解

本文研究了复合图１－因子分解问题，给出了复合图可１－因子分解的几个充分条件．设图Ｇ和Ｈ都是正则因，那么Ｇ和Ｈ的复合图Ｇ［Ｈ］可１－因子分解，如果Ｇ和Ｈ满足下列三个条件之一：（１）Ｇ可１－因子分解；（２）Ｇ至少有　１－因子，Ｈ为偶阶正则图［Ｖ（Ｈ）｜≥２；（３）Ｇ可以分解为一些１－因子和２－因子之并，Ｈ为偶阶正则图且至少有ｍａｘ｛０，△（Ｈ）－４｝个１－因子．     

关于图的（g，f）－因子分解的一些新结果

本文讨论图的（ｇ，ｆ）－因子分解问题，推广了文［１］关于图的因子分解的理论，改进了文［２］的一些结果，给出了一个图Ｇ是（ｇ，ｆ）－可因子化的若干充分条件．     

关于正交因子分解的一些结果

设G是一个图,F={F_1,F_2,…,F_d}是G的一个因子分解,H是C的一个子图,若H有d条边且恰好与每个F_i有一条公共边,则称H与F是正交的。本文研究了与图的K-因子分解正交的对集及[a,b]-子图,从而证明了关于因子分解问题的两个猜想在某些情况下成立,并提出了可进一步研究的问题。     

关于图的（g,f）—因子分解的一些新结果

本文讨论图的（ｇ，ｆ）－因子分解问题，推广了文「１」关于图的因子分解的理论，改进了文「２」的一些结果，给出了一个图Ｇ是（ｇ，ｆ）－可因子化的若干充分条件。     

与任意图正交的[0,ki]1^m—因子分解

设G是一个图,k1,…,km,是正整数,若图G的边能分解成m个边不交的[0,k1]-因子 F1,…,[0,]-l因子Fm,则称F＝{F1,…,Fm}是G 的一个[0,ki]1^m-因子分解,如果H是G的一个有m条边的了了图且对任意的1≤i≤m有E（H）E（Fi)=1,则称F与H正交,证明了若G是一个[0,k1 ,…, km-m 1]-图,。H是G的一个有m条边的子图,则图G有一个[0,ki]1^m-因子分解与H正交。     

图的分数(g,f)-因子

本文研究了图的分数因子的性质,特别给出了图的弧立韧度这一新概念,研究了孤立韧度与分数因子的关系,文中给出了一个图具有某些约束条件的（g,f）-分数因子的一些充分条件,得到了若干新结果,并提出 了一些可供进一步研究的问题。     

图的色因子分解

设 ｎ１ ≥ ｎ ２ ≥ … ≥ ｎｋ ≥ ２ 是整数． 若图 Ｇ 能边分解成 Ｇ１  Ｇ２  …  Ｇｋ , 这里 χ（ Ｇｉ） ＝ ｎ ｉ, ｉ＝１,２,…,ｋ ,则称 Ｇ 有（ｎ１ , ｎ２ , …, ｎｋ ）色因子 分解． 本文改进 了 Ｈａｋｉｍ ｉ和 Ｓｃｈｍ ｅｉｃｈ ｅｌ 关于图的色因 子分解的结果,作为推 论,推广了 Ｍ ａｔｕｌａ 和 Ｈａｒａｒｙ 等人的结果     

与任意图正交的［0，ki］m1-因子分解

设G是一个图, k1,…, km是正整数.若图G的边能分解成m个边不交的［0,k1］-因子 F1,…,［0,km］-因子Fm,则称＝F1,…,Fm是G的一个［0,ki］m1-因子分解.如果H是G的一个有m条边的子图且对任意的1≤I≤m有｜E(H)∩E(Fi)｜＝1,则称与H正交.证明了若G是一个［0,k1＋…＋km－m＋1］-图,H是G的一个有m条边的子图,则图G有一个［0,ki］m1-因子分解与H正交.     

与任意图正交的[0,k_i]_1~m-因子分解

设G是一个图 ,k1,… ,km 是正整数·　若图G的边能分解成m个边不交的 [0 ,k1]_因子F1,… ,[0 ,km]_因子Fm,则称 F =F1,… ,Fm 是G的一个 [0 ,ki]m1_因子分解·　如果H是G的一个有m条边的子图且对任意的 1≤i≤m有｜E(H) ∩E(Fi) ｜=1,则称 F与H正交·　证明了若G是一个 [0 ,k1 … km-m 1]_图 ,H是G的一个有m条边的子图 ,则图G有一个 [0 ,ki]m1_因子分解与H正交     

图中推广的正交因子分解

设G是一个图,具有顶点集合V(G)和边集合E(G).设g和f是定义在V(G)上的整数值函数,使对每个x∈V(G),有g(x)≤f(x).图G的一个(g,f)-因子是G的一个支撑子图H,使对每个x∈V(G),有g(x)≤d_H(x)≤f(x).G的一个(g,f)-因子分解是E(G)的边不相交的(g,g)-因子的一个划分.设F={F-1,F_2,…,F_m}为G的一个因子分解,H是G的一个有mr条边的子图.如果每个F_i恰好与H有r条公共边,1≤i≤m,则称Fr-正交于H.本文证明每个(mg+kr,mf-kr)-图含有一个子图R,使R有(g,f)-因子分解r-正交于任意给定的有kr条边的子图,其中m,k和r为正整数且k相似文献   

Unbalanced bipartite factorizations of complete bipartite graphs

We construct a new infinite family of factorizations of complete bipartite graphs by factors all of whose components are copies of a (fixed) complete bipartite graph K_p,q. There are simple necessary conditions for such factorizations to exist. The family constructed here demonstrates sufficiency in many new cases. In particular, the conditions are always sufficient when q=p+1.     

On perfectly two-edge connected graphs

This paper studies the graphs for which the 2-edge connected spanning subgraph polytope is completely described by the trivial inequalities and the so-called cut inequalities. These graphs are called perfectly 2-edge connected. The class of perfectly 2-edge connected graphs contains for instance the class of series-parallel graphs. We introduce a new class of perfectly 2-edge connected graphs. We discuss some structural properties of graphs which are (minimally with respect to some reduction operations) nonperfectly 2-edge connected. Using this we give sufficient conditions for a graph to be perfectly 2-edge connected.     

Marginal AMP chain graphs

We present a new family of models that is based on graphs that may have undirected, directed and bidirected edges. We name these new models marginal AMP (MAMP) chain graphs because each of them is Markov equivalent to some AMP chain graph under marginalization of some of its nodes. However, MAMP chain graphs do not only subsume AMP chain graphs but also multivariate regression chain graphs. We describe global and pairwise Markov properties for MAMP chain graphs and prove their equivalence for compositional graphoids. We also characterize when two MAMP chain graphs are Markov equivalent.For Gaussian probability distributions, we also show that every MAMP chain graph is Markov equivalent to some directed and acyclic graph with deterministic nodes under marginalization and conditioning on some of its nodes. This is important because it implies that the independence model represented by a MAMP chain graph can be accounted for by some data generating process that is partially observed and has selection bias. Finally, we modify MAMP chain graphs so that they are closed under marginalization for Gaussian probability distributions. This is a desirable feature because it guarantees parsimonious models under marginalization.     

(向量)R_n和(向量)G_n的有向优美性

优美图可用在图论中的某些H-分解问题中,很多人研究无向图的优美标号.研究有向优美标号,通过对阶数奇偶性的讨论,给出了n(≥2)阶有向路(向量)P_n和n(≥3)阶有向(向量)C_n圈是有向优美的充分条件.     

Eulerian detachments with local edge-connectivity

For a graph G, a detachment operation at a vertex transforms the graph into a new graph by splitting the vertex into several vertices in such a way that the original graph can be obtained by contracting all the split vertices into a single vertex. A graph obtained from a given graph G by applying detachment operations at several vertices is called a detachment of graph G. While detachment operations may decrease the connectivity of graphs, there are several works on conditions for preserving the connectivity. In this paper, we present necessary and sufficient conditions for a given graph/digraph to have an Eulerian detachment that satisfies a given local edge-connectivity requirement. We also discuss conditions for the detachment to be loopless.     

无K1,r图中的哈密顿圈（英文）

本文借助对图的本质独立集和图的部分平方图的独立集的研究，对于K1,r图中哈密顿圈的存在性给出了八个充分条件。我们将利用T－插点技术对这八个充分条件给出统一的证明，本文的结果从本质上改进了C－Q.Zhang于1988年利用次形条件给出的k-连通无爪图是哈密顿图的次型充分条件，同时。G.Chen和R.H.Schelp在1995年利用次型条件给出的关于k-连通无K1，4图是哈密顿图的充分条件也被我们的结果改进并推广到无K1,r图。     

On transitive one-factorizations of arc-transitive graphs

It is shown that transitive 1-factorizations of arc-transitive graphs exist if and only if certain factorizations of their automorphism groups exist. This relation provides a method for constructing and characterizing transitive 1-factorizations for certain classes of arc-transitive graphs. Then a characterization is given of 2-arc-transitive graphs which have transitive 1-factorizations. In this characterization, some 2-arc transitive graphs and their transitive 1-factorizations are constructed.     

An algorithm for constructing star-shaped drawings of plane graphs

A straight-line planar drawing of a plane graph is called a convex drawing if every facial cycle is drawn as a convex polygon. Convex drawings of graphs is a well-established aesthetic in graph drawing, however not all planar graphs admit a convex drawing. Tutte [W.T. Tutte, Convex representations of graphs, Proc. of London Math. Soc. 10 (3) (1960) 304–320] showed that every triconnected plane graph admits a convex drawing for any given boundary drawn as a convex polygon. Thomassen [C. Thomassen, Plane representations of graphs, in: Progress in Graph Theory, Academic Press, 1984, pp. 43–69] gave a necessary and sufficient condition for a biconnected plane graph with a prescribed convex boundary to have a convex drawing.In this paper, we initiate a new notion of star-shaped drawing of a plane graph as a straight-line planar drawing such that each inner facial cycle is drawn as a star-shaped polygon, and the outer facial cycle is drawn as a convex polygon. A star-shaped drawing is a natural extension of a convex drawing, and a new aesthetic criteria for drawing planar graphs in a convex way as much as possible. We give a sufficient condition for a given set A of corners of a plane graph to admit a star-shaped drawing whose concave corners are given by the corners in A, and present a linear time algorithm for constructing such a star-shaped drawing.     

On conservative and supermagic graphs

A graph is called supermagic if it admits a labelling of the edges by pairwise different consecutive positive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. A graph G is called conservative if it admits an orientation and a labelling of the edges by integers {1,…,|E(G)|} such that at each vertex the sum of the labels on the incoming edges is equal to the sum of the labels on the outgoing edges. In this paper we deal with conservative graphs and their connection with the supermagic graphs. We introduce a new method to construct supermagic graphs using conservative graphs. Inter alia we show that the union of some circulant graphs and regular complete multipartite graphs are supermagic.