Bipartite Divisor Graphs for Integer Subsets

Inspired by connections described in a recent paper by Mark L. Lewis, between the common divisor graph Γ(X) and the prime vertex graph Δ(X), for a set X of positive integers, we define the bipartite divisor graph B(X), and show that many of these connections flow naturally from properties of B(X). In particular we establish links between parameters of these three graphs, such as number and diameter of components, and we characterise bipartite graphs that can arise as B(X) for some X. Also we obtain necessary and sufficient conditions, in terms of subconfigurations of B(X), for one of Γ(X) or Δ(X) to contain a complete subgraph of size 3 or 4.     

Bounds on Special Subsets in Graphs, Eigenvalues and Association Schemes

We give a bound on the sizes of two sets of vertices at a given minimum distance in a graph in terms of polynomials and the Laplace spectrum of the graph. We obtain explicit bounds on the number of vertices at maximal distance and distance two from a given vertex, and on the size of two equally large sets at maximal distance. For graphs with four eigenvalues we find bounds on the number of vertices that are not adjacent to a given vertex and that have µ common neighbours with that vertex. Furthermore we find that the regular graphs for which the bounds are tight come from association schemes.     

图的既无孤立点也无内点的非空闭子集的结构

借助于拓扑加群∑2的齐性,本给出了如下定理的一个证明：任一个图G上的任一既无孤立点也无内点的非空闭子集均是个Cantor集。     

Sum-Avoiding Subsets

We estimate the maximal number of elements that can be selected from a set of n numbers so that the sum of two selected elements are never in the original set. We improve Choi’s upper bound of n^2/5 to e^{c√log n n}.To Professor Nicolas, on the occasion of his 60th birthday.2000 Mathematics Subject Classification: Primary—11B75Supported by Hungarian National Foundation for Scientific Research (OTKA), Grants No. T 38396, T43623 and T42750.     

Symmetric Graphs and Flag Graphs

 With any G-symmetric graph Γ admitting a nontrivial G-invariant partition , we may associate a natural “cross-sectional” geometry, namely the 1-design in which for and if and only if α is adjacent to at least one vertex in C, where and is the neighbourhood of B in the quotient graph of Γ with respect to . In a vast number of cases, the dual 1-design of contains no repeated blocks, that is, distinct vertices of B are incident in with distinct subsets of blocks of . The purpose of this paper is to give a general construction of such graphs, and then prove that it produces all of them. In particular, we show that such graphs can be reconstructed from and the induced action of G on . The construction reveals a close connection between such graphs and certain G-point-transitive and G-block-transitive 1-designs. By using this construction we give a characterization of G-symmetric graphs such that there is at most one edge between any two blocks of . This leads to, in a subsequent paper, a construction of G-symmetric graphs such that and each is incident in with vertices of B. The work was supported by a discovery-project grant from the Australian Research Council. Received April 24, 2001; in revised form October 9, 2002 Published online May 9, 2003     

Almost Convex Subsets

We study almost convex subsets of spaces with one-sided curvature bounds. We derive some characterisations and properties of sets of positive reach in Riemannian manifolds.     

Subsets and subspaces

Several rules known to be valid within the set theory are revisited and considered from the point of view of the question whether they remain satisfied when sets are replaced with subspaces from C_n,1. It is shown that some of the set relationships hold true upon such a replacement, however, there is also an extensive class of relationships whose validity is no longer guaranteed; in this class the commutativity of the orthogonal projectors onto the involved subspaces proves to play an important role. Some related results inspired by probability theory are established as well.     

Isosceles Planar Subsets

A finite planar set is k -isosceles for k ≥ 3 if every k -point subset of the set contains a point equidistant from two others. There are three nonsimilar 3-isosceles sets with five points and one with six points. Eleven 4-isosceles sets with eight points are noted, and it is conjectured that no 4-isosceles set has nine points. Exactly one 4-isosceles 8-set has four points on a line, and every 4-isosceles set that includes the vertices of a square has fewer than eight points. <lsiheader> <onlinepub>26 June, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>19n3p391.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>yes <sectionname> </lsiheader> Received February 1, 1997, and in revised form June 24, 1997.     

可数SP-紧子集

针对一般的L-子集在L-拓扑空间中引入了可数SP-紧性和SP-Lindelof性质的概念,研究了它们的基本性质和特征性质。     

无向路图和块图上的混合控制

图G=(V,E)的一个混合控制集是一个满足如下条件的集合DV∪E:不在D中的每个点或每条边都相邻或关联于D中的至少一个点或一条边.确定图的最小基数的混合控制集的问题称为混合控制问题.本文研究混合控制问题的算法复杂性,证明了混合控制问题在无向路图上是NP-完全的,但在块图上有线性时间算法.无向路图和块图都是弦图的子类,又是树的母类.     

图的边韧性度

文[1]中,定义图G(V,E)的边韧性度定义为min{(|S|+T(G-S))/(ω(G-S)):S?E(G)},这里,T-(G-S)和ω(G-S)分别表示G-S中最大分支的顶点数和连通分支数.这是一个能衡量网络图稳定性较好的参数,因为它不仅考虑到了图G-S的分支数也考虑到了它的阶数.在以前的工作中,作者得到了边韧性度图的一个充要条件.利用这些结果证明了K-树是严格边韧性度图,并找到了边韧性度与较高阶的边坚韧度和边坚韧度之间的关系.     

双线性型图与交错型图不是完美图

本文证明了双线性型图与交错型图都不是完美图,从而解决了双线性型图与交错型图的完美图判别问题.     

Diamond-Free Subsets in the Linear Lattices

Four distinct elements a, b, c, and d of a poset form a diamond if \(a< b and \(a . A subset of a poset is diamond-free if no four elements of the subset form a diamond. Even in the Boolean lattices, finding the size of the largest diamond-free subset remains an open problem. In this paper, we consider the linear lattices—poset of subspaces of a finite dimensional vector space over a finite field of order q—and extend the results of Griggs et al. (J. Combin. Theory Ser. A 119(2):310–322, 2012) on the Boolean lattices, to prove that the number of elements of a diamond-free subset of a linear lattice can be no larger than \(2+\frac {1}{q+1}\) times the width of the lattice, so that this fraction tends to 2 as \(q \longrightarrow \infty \) . In addition, using an algebraic technique, we introduce so-called diamond matchings, and prove that for linear lattices of dimensions up to 5, the size of a largest diamond-free subset is equal to the sum of the largest two rank numbers of the lattice.     

蛛网图及渔网图的邻点可区别I-全染色

通过揭示完全蛛网图和渔网图的结构特点,研究了它们的邻点可区别I-全染色问题,并运用构造法给出了其邻点可区别I-全染色,从而获得了它们的邻点可区别I-全色数.