3-一致超图的反馈数研究

超图H=(V,E)顶点集为V,边集为E.S■V是H的顶点子集,如果H/S不含有圈,则称S是H的点反馈数,记τc(H)是H的最小点反馈数.本文证明了:(i)如果H是线性3-一致超图,边数为m,则τc(H)≤m/3;(ii)如果H是3-一致超图,边数为m,则τc(H)≤m/2并且等式成立当且仅当H任何一个连通分支是孤立顶点或者长度为2的圈.A■V是H的边子集,如果H\A不含有圈,则称A是H的边反馈数,记τc′(H)是H的最小边反馈数.本文证明了如果H是含有p个连通分支的3-一致超图,则τc’(H)≤2m-n+p.     

图中推广的正交因子分解

设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相似文献   

Antimagic Labelings of Join Graphs

An antimagic labeling of a graph with q edges is a bijection from the set of edges of the graph to the set of positive integers \({\{1, 2,\dots,q\}}\) such that all vertex weights are pairwise distinct, where a vertex weight is the sum of labels of all edges incident with the vertex. The join graph G + H of the graphs G and H is the graph with \({V(G + H) = V(G) \cup V(H)}\) and \({E(G + H) = E(G) \cup E(H) \cup \{uv : u \in V(G) {\rm and} v \in V(H)\}}\). The complete bipartite graph K _m,n is an example of join graphs and we give an antimagic labeling for \({K_{m,n}, n \geq 2m + 1}\). In this paper we also provide constructions of antimagic labelings of some complete multipartite graphs.     

5-一致超图的全横贯

设H=(V,E)是以V为顶点集, E为(超)边集的超图. 如果H的每条边均含有k个顶点, 则称H是k-一致超图. 超图H的点子集T称为它的一个横贯, 如果T 与H 的每条边均相交. 超图H的全横贯是指它的一个横贯T, 并且T还满足如下性质: T中每个顶点均至少有一个邻点在T中. H 的全横贯数定义为H 的最小全横贯所含顶点的数目, 记作\tau_{t}(H). 对于整数k\geq 2, 令b_{k}=\sup_{H\in{\mathscr{H}}_{k}}\frac{\tau_{t}(H)}{n_{H}+m_{H}}, 其中n_H=|V|, m_H=|E|, {\mathscr{H}}_{k} 表示无孤立点和孤立边以及多重边的k-一致超图类. 最近, Bujt\'as和Henning等证明了如下结果: b_{2}=\frac{2}{5}, b_{3}=\frac{1}{3}, b_{4}=\frac{2}{7}; 当k\geq 5 时, 有b_{k}\leq \frac{2}{7}以及b_{6}\leq \frac{1}{4}; 当k\geq 7 时, b_{k}\leq \frac{2}{9}. 证明了对5-一致超图, b_{5}\leq \frac{4}{15}, 从而改进了当k=5 时b_k的上界.     

On unavoidable hypergraphs

A r-uniform hypergraph H (or a r-graph, for short) is a collection E = E(H) of r-element subsets (called edges) of a set V = V(H) (called vertices). We say a r-graph H is (n, e)-unavoidable if every r-graph with n vertices and e edges must contain H. In this paper we investigate the largest possible number of edges in an (n, e)-unavoidable 3-graph for fixed n and e. We also study the structure of such unavoidable 3-graphs.     

Bounds related to domination in graphs with minimum degree two

A dominating set for a graph G = (V,E) is a subset of vertices V′ ⊆ V such that for all v E V − V′ there exists some u E V′ for which {v, u} E E. The domination number of G is the size of its smallest dominating set(s). We show that for almost all connected graphs with minimum degree at least 2 and q edges, the domination number is bounded by (q + 1)/3. From this we derive exact lower bounds for the number of edges of a connected graph with minimum degree at least 2 and a given domination number. We also generalize the bound to k-restricted domination numbers; these measure how many vertices are necessary to dominate a graph if an arbitrary set of k vertices must be incluced in the dominating set. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 139–152, 1997     

图的邻接矩阵的行列式与积和式的递推表达式

设A(G)是简单图G的邻接矩阵,H是由G的独立边和不交圈组成的生成子图的集合,e是H中某个图的独立边,C是H中图的圈,且e∈E(C).记G-e是G的删边子图,G\W是从G中删去导出子图W中的顶点及其关联边后得到的图.那么A(G)的行列式为detA(G)=detA(G-e)-detA(G\e)-2(-1)~(|V(C)|)detA(G\C)A(G)的积和式为perA(G)=perA(G-e)+perA(G\e)+2perA(G\C)这里,C取遍H中图的经过边e的圈.     

平面图的k-重(2k+2)-染色

G=(V,E)表示一个顶点集为V,边集为E的有限简单无向图.若存在映射φ:V(G)→Zk(n)(Zk(n)是由{1,2,…,n}的所有k-元子集构成的集合),满足:(A) uv∈E(G),有φ(u)∩φ(u)=θ,则称φ是G的一个k-重n-顶点染色.本文证明了奇围长至少为5k-7(k=4)或5k-9(k=6)的平面图G...     

最大度为7 且不含带弦5- 圈的平面图是8- 全可染的

若能用k种颜色给图的顶点和边同时进行染色使得相邻或相关联的元素(顶点或边) 染不同的色, 则称这个图是k- 全可染的. 显然, 给最大度为Δ的图进行全染色, 至少要用Δ + 1 种不同的色.本文证明最大度为7 且不含带弦5- 圈的平面图是8- 全可染的. 这一结果进一步拓广了(Δ+1)- 全可染图类.     

某些中间图的邻点可区别E-全色数

设G（V,E）是简单连通图,T（G）为图G的所有顶点和边构成的集合,并设C是k-色集（k是正整数）,若T（G）到C的映射f满足：对任意uv∈E（G）,有f（u）≠f（v）,f（u）≠f（uv）,f（v）≠f（uv）,并且C（u）≠C（v）,其中C（u）={f（u）}∪{f（uv）｜uv∈E（G）}.那么称f为图G的邻点可区别E-全染色（简记为k-AVDETC）,并称χ_（at）~e（G）=min{k｜图G有k-邻点可区别E-全染色}为G的邻点可区别E-全色数.图G的中间图M（G）就是在G的每一个边上插入一个新的顶点,再把G上相邻边上的新的顶点相联得到的.探讨了路、圈、扇、星及轮的中间图的邻点可区别E-全染色,并给出了这些中间图的邻点可区别E-全色数.     

On the edge-binding number of some plane graphs

1. IntroductionSince WOodall gave out the concept of biIldi11g Ilu1lJber in 1973[l] ! the bil1ding nunlber fOrsome specia1 classes have beeIl studied by Kane and WaIlg Jianfang[']. Mirolawa Skowronskahave studied the binding number of Halin-graph[']. ZI1ang Zhongfu, Liu Li1lzhong andZhang Jianxun have extended the bil1di11g nuInber to the edges and studied tlle edge-bindingnumber of path, cycle, coInplete grapl1. I1l this paper, we study the edge-binding number ofouter plane graph, Ha…     

Total restrained bondage in graphs

A subset S of vertices of a graph G with no isolated vertex is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex in V (G) S is also adjacent to a vertex in V (G) S. The total restrained domination number of G is the minimum cardinality of a total restrained dominating set of G. In this paper we initiate the study of total restrained bondage in graphs. The total restrained bondage number in a graph G with no isolated vertex, is the minimum cardinality of a subset of edges E such that G E has no isolated vertex and the total restrained domination number of G E is greater than the total restrained domination number of G. We obtain several properties, exact values and bounds for the total restrained bondage number of a graph.     

关联聚类问题的半定规划舍入算法

主要研究带有两类权重的一般图下的关联聚类问题. 问题的定义是, 给定图G=(V,E), 每条边有两类权重, 我们需要将点集V进行聚类, 目标是最大相同性, 即最大化属于某个类的边的第一类权重之和加上在两个不同类之间的边的第二类权重之和. 该问题是NP-难的, 我们利用外部旋转技术将现有的半定规划舍入0.75-近似算法改进. 算法的分析指出, 改进的算法虽然不能将近似比0.75提高, 但是对于大多数实例, 可以获得更好的运行效果.     

Neighbor sum distinguishing list total coloring of IC-planar graphs without 5-cycles

Czechoslovak Mathematical Journal - Let G = (V(G), E(G)) be a simple graph and EG(υ) denote the set of edges incident with a vertex υ. A neighbor sum distinguishing (NSD) total coloring...     

关于E0的Steiner邮路问题

给定图G＝(V，E，ω)，E0真包含于E是是一个指定通过的边子集，本文讨论了关于E0的Steiner邮路问题的特殊情况，即由E0导出的子图仅有两个连通分支．我们分别考虑了三种不同的情形，并给出了子闭迹消去算法和带限制的最短链算法，前者是一个基于整数规划的精确算法，而后者是一个近似算法．     

不含三角形的图的λ3-最优性的充分条件

设G=(V,E)是一个连通图,边集S(?)E是一个3-限制性边割,如果G-S是不连通的并且G-S的每个分支至少有三个点.图G的3-限制性边连通度λ_3(G)是G中最小的一个3-限制性边割的基数.图G是λ_3(G)连通的,如果3-限制性边割存在.G是λ_3-最优的,如果λ_3(G)=ξ_3(G),其中ξ_3(G)=min{|[U,(?)]|:U(?)V,|U|=3 and G[U]是连通的).G[U]表示V的子集U的导出子图,(?)=V\U表示U的补.[U,(?)]是一条边的一个端点在U中另一个端点在(?)中的边的集合.本文给出了不含三角形的图是λ_3-最优的一些充分条件.     

关于图中子图的（n,k）—正交因子分解

设G是一个具有顶点集V(G)和边集E(G)的图. 设g和f是定义在V(G)上的两个整数值函数,使得g(x)f(x)对所有的点x∈V(G)都成立.如果G是一个(mg+n,mf-n)-图,1n<m2k,且g(x)2k-1对所有的点x∈V(G)都成立,则对任意给定具有|E(H)|=nk边的G的子图H,存在G的一个子图G′使G′有一个(g,f)-因子分解(n,k)-正交H.     

图是超限制性边连通的充分条件

设G=（V,E）是连通图.边集S E是一个限制性边割,如果G-S是不连通的且G—S的每个分支至少有两个点.G的限制性连通度λ＇（G）是G的一个最小限制性边割的基数.G是λ＇-连通的,如果G存在限制性边割.G是λ＇-最优的,如果λ＇（G）=ζ（G）,其中ζ（G）是min{d（x）＋d（y）-2：xy是G的一条边}.进一步,如果每个最小的限制性边割都孤立一条边,则称G是超限制性边连通的或是超-λ＇.G的逆度R（G）=∑_（v∈V） 1/d（v）,其中d（v）是点v的度数.我们证明了G是λ＇-连通的且不含三角形,如果R（G）≤2＋1/ζ-ζ/（（2δ-2）（2δ-3））＋（n-2δ-ζ＋2）/（（n-2δ＋1）（n-2δ＋2））,则G是超-λ＇.     

Computing the Degree-4 Shortest Network under a Given Topology

Let F be a set of n (n being an even number) fixed points and let M be a set of n / 2 -1 moving points, whose locations are to be determined, in the plane. A topology is a set of edges connecting these points in the set V=F\cup M . Let E be a full 4-degree Steiner topology; i.e., the topology forms a tree which contains fixed points of degree 1 and moving points of degree 4, and let H(E) be a set of topologies which include E and its degeneracies. We define a canonical tree over V as one whose topology belongs to H(E) and in which the sum of two adjacent angles around any node is not less than π . In this paper we prove that if a canonical tree exists, then it is the shortest (degree-4) network under a given topology E . We present an O(n ² ) time algorithm for finding a degree-4 shortest network whose topology belongs to H(E) . Received November 16, 1998.     

二分（0，mf—m＋1）-图的正交（0，f）-因子分解

设G=（X,Y,E（G））是一个二分图,分别用V（G）=X∪Y和E（G）表示G的顶点集和边集．设f是定义在V（G）上的整数值函数且对任意x∈V（G）有f（x）≥k．设H1,H2,…,Hk是G的k个顶点不相交的子图,且｜E（Hi）｜=m,1≤i≤k．本文证明了每个二分（0,mf—m＋1）．图G有一个（0,f）-因子分解正交于Hi（i=1,2,…,k）