A Note on Hitting Maximum and Maximal Cliques With a Stable Set

It was recently proved that any graph satisfying contains a stable set hitting every maximum clique. In this note, we prove that the same is true for graphs satisfying unless the graph is the strong product of an odd hole and .We also provide a counterexample to a recent conjecture on the existence of a stable set hitting every sufficiently large maximal clique.     

Cliques in dense inhomogeneous random graphs

The theory of dense graph limits comes with a natural sampling process which yields an inhomogeneous variant of the Erd?s–Rényi random graph. Here we study the clique number of these random graphs. We establish the concentration of the clique number of for each fixed n , and give examples of graphons for which exhibits wild long‐term behavior. Our main result is an asymptotic formula which gives the almost sure clique number of these random graphs. We obtain a similar result for the bipartite version of the problem. We also make an observation that might be of independent interest: Every graphon avoiding a fixed graph is countably‐partite. © The Authors Random Structures & Algorithms Published byWiley Periodicals, Inc. Random Struct. Alg., 2016 © 2017 The Authors Random Structures & Algorithms Published by Wiley Periodicals, Inc. Random Struct. Alg., 51, 275–314, 2017     

Maximal Induced Matchings in Triangle‐Free Graphs

An induced matching in a graph is a set of edges whose endpoints induce a 1‐regular subgraph. It is known that every n‐vertex graph has at most  maximal induced matchings, and this bound is the best possible. We prove that every n‐vertex triangle‐free graph has at most  maximal induced matchings; this bound is attained by every disjoint union of copies of the complete bipartite graph K_{3, 3}. Our result implies that all maximal induced matchings in an n‐vertex triangle‐free graph can be listed in time , yielding the fastest known algorithm for finding a maximum induced matching in a triangle‐free graph.     

导出匹配,极大导出匹配可扩图和导出匹配数

目前我们已知的极大导出匹配可扩图只有Kn,n和K2n.为了研究它们是否是仅有的极大导出匹配可扩图,我们考虑了匹配数,导出匹配数,极大导出匹配可扩图以及一个相关的猜想,并得出了若干相关的结果.     

一类直径为2的极大平面图的Mostar指数

图G的Mostar指数定义为Mo(G)=∑uv∈Ε(G)|nu-nv|,其中nu表示在G中到顶点u的距离比到顶点v的距离近的顶点个数,nv表示到顶点v的距离比到顶点u的距离近的顶点个数.若一个图G的任两点之间的距离至多为2,且不是完全图,则称G是一个直径为2的图.已知直径为2点数至少为4的极大平面图的最小度为3或4.本文研究了直径为2且最小度为4的极大平面图的Mostar指数.具体说,若G是一个点数为n,直径为2,最小度为4的极大平面图,则(1)当n≤12时,Mostar指数被完全确定;(2)当n≥13时,4/3n2-44/3n+94/3≤Mo(G)≤2n2-16n+24,且达到上,下界的极图同时被找到.     

极大非独立集可削去的因子临界图

如果对一个简单图G的每一个与G的顶点数同奇偶的独立集I，都有G-I有完美匹配，则称G是独立集可削去的因子临界图．如果图G不是独立集可削去的因子临界图，而对任意两个小相邻的顶点x与y，G xy足独立集可削去的因子临界图，则称G足极大非独立集可削去的因子临界图，本刻画了极大非独立集可削去的因子临界图。     

门槛图与度极大图

证明了门槛图与度极大图是一类图的两种不同说法,同时用图的对角限制极左矩阵刻画这一类图的结构。     

Minimum Degrees of Minimal Ramsey Graphs for Almost‐Cliques

For graphs F and H, we say F is Ramsey for H if every 2‐coloring of the edges of F contains a monochromatic copy of H. The graph F is Ramsey H‐minimal if F is Ramsey for H and there is no proper subgraph of F so that is Ramsey for H. Burr et al. defined to be the minimum degree of F over all Ramsey H‐minimal graphs F. Define to be a graph on vertices consisting of a complete graph on t vertices and one additional vertex of degree d. We show that for all values ; it was previously known that , so it is surprising that is much smaller. We also make some further progress on some sparser graphs. Fox and Lin observed that for all graphs H, where is the minimum degree of H; Szabó et al. investigated which graphs have this property and conjectured that all bipartite graphs H without isolated vertices satisfy . Fox et al. further conjectured that all connected triangle‐free graphs with at least two vertices satisfy this property. We show that d‐regular 3‐connected triangle‐free graphs H, with one extra technical constraint, satisfy ; the extra constraint is that H has a vertex v so that if one removes v and its neighborhood from H, the remainder is connected.     

Fuzzy图最大树聚类方法及其应用

针对《中国大学评价》中9所交通院校,应用距离补公式计算出Fuzzy关系矩阵,画出Fuzzy图,找出最大树,选取适当的阈值λ对最大树进行截割,得到λ水平上的分类.在此基础上对这9所学校进行合理的分类.     

Finding Postal Carrier Walk Paths in Mixed Graphs

The postman problem requires finding a lowest cost tour in a connected graph that traverses each edge at least once. In this paper we first give a brief survey of the literature on postman problems including, the original Chinese postman problem on undirected graphs, the windy Chinese postman problem on graphs where the cost of an arc depends on the direction the arc is transversed, the directed postman problem on graphs with directed edges, and the mixed postman problem on graphs in which there are some directed and some undirected arcs.We show how the mixed postman problem can be solved as an integer program, using the formulation of Gendreau, Laporte and Zhao, by a new row addition branch and bound algorithm, which is a modification of the column subtraction algorithm for set partitioning problems of Harche and Thompson. Computational experience shows that a slack variable heuristic is very effective in finding good solutions that are frequently optimal for these problems.     

A Polynomial-Time Algorithm for Finding Regular Simple Paths in Outerplanar Graphs

Let G be a labeled directed graph with arc labels drawn from alphabet Σ, R be a regular expression over Σ, and x and y be a pair of nodes from G. The regular simple path (RSP) problem is to determine whether there is a simple path p in G from x to y, such that the concatenation of arc labels along p satisfies R. Although RSP is known to be NP-hard in general, we show that it is solvable in polynomial time when G is outerplanar. The proof proceeds by presenting an algorithm which gives a polynomial-time reduction of RSP for outerplanar graphs to RSP for directed acyclic graphs, a problem which has been shown to be solvable in polynomial time.     

Minimally k-Edge-Connected Directed Graphs of Maximal Size

Let D=(V,E) be a minimally k-edge-connected simple directed graph. We prove that there is a function f(k) such that |V|f(k) implies |E|2k(|V|–k). We also determine the extremal graphs whose size attains this upper bound.Basic Research in Computer Science, funded by the Danish National Research Foundation.Supported by the MTA-ELTE Egerváry Research Group on Combinatorial Optimization, and the Hungarian Scientific Research Fund grant No. F034930, T037547, and FKFP grant No. 0143/2001. Part of this research was done when the second author visited BRICS, University of Aarhus, Denmark.     

The Complete Chromatic Number of Maximal Outerplane Graphs

Let G be a maximal outerplane graph and X0(G) the complete chromatic number of G. This paper determines exactly X0(G) for △(G)≠5 and proves 6≤X0.(G)≤7 for △(G) = 5, where △(G) is the maximum degree of vertices of G.     

Large Cliques in -Free Graphs

Dedicated to the memory of Paul Erdős A graph is called -free if it contains no cycle of length four as an induced subgraph. We prove that if a -free graph has n vertices and at least edges then it has a complete subgraph of vertices, where depends only on . We also give estimates on and show that a similar result does not hold for H-free graphs––unless H is an induced subgraph of . The best value of is determined for chordal graphs. Received October 25, 1999 RID="*" ID="*" Supported by OTKA grant T029074. RID="**" ID="**" Supported by TKI grant stochastics@TUB and by OTKA grant T026203.     

Coloring of Plane Graphs with Unique Maximal Colors on Faces

The Four Color Theorem asserts that the vertices of every plane graph can be properly colored with four colors. Fabrici and Göring conjectured the following stronger statement to also hold: the vertices of every plane graph can be properly colored with the numbers 1, …, 4 in such a way that every face contains a unique vertex colored with the maximal color appearing on that face. They proved that every plane graph has such a coloring with the numbers 1, …, 6. We prove that every plane graph has such a coloring with the numbers 1, …, 5 and we also prove the list variant of the statement for lists of sizes seven.     

Local Clique Covering of Claw‐Free Graphs

A clique covering of a simple graph G is a collection of cliques of G covering all the edges of G such that each vertex is contained in at most k cliques. The smallest k for which G admits a clique covering is called the local clique cover number of G and is denoted by lcc(G). Local clique cover number can be viewed as the local counterpart of the clique cover number that is equal to the minimum total number of cliques covering all edges. In this article, several aspects of the local clique covering problem are studied and its relationships to other well‐known problems are discussed. In particular, it is proved that the local clique cover number of every claw‐free graph is at most , where Δ is the maximum degree of the graph and c is a constant. It is also shown that the bound is tight, up to a constant factor. Moreover, regarding a conjecture by Chen et al. (Clique covering the edges of a locally cobipartite graph, Discrete Math 219(1–3)(2000), 17–26), we prove that the clique cover number of every connected claw‐free graph on n vertices with the minimum degree δ, is at most , where c is a constant.     

区间模糊ISODATA动态聚类算法

目前模糊技术已经应用于许多智能系统,如模糊关系与模糊聚类.聚类是数据挖掘的重要任务,它将数据对像分成多个聚类,在同一个聚类中,对象的属性特征之间具有较高的相似度,有很大研究及应用价值.结合数据库中的挖掘技术,对属性特征为区间数的多属性决策问题,提出了一种基于区间数隶属度的区间模糊ISODATA动态聚类方法.     

直径不超过2的2连通无爪图是哈密顿图

不包含2K_2的图是指不包含一对独立边作为导出子图的图.Kriesell证明了所有4连通的无爪图的线图是哈密顿连通的.本文证明了如果图G不包含2K_2并且不同构与K_2,P_3和双星图,那么线图L(G)是哈密顿图,进一步应用由Ryjá(?)ek引入的闭包的概念,给出了直径不超过2的2连通无爪图是哈密顿图这个定理的新的证明方法.