On the generation of bicliques of a graph

An independent set of a graph is a subset of pairwise non-adjacent vertices. A complete bipartite set B is a subset of vertices admitting a bipartition B=X∪Y, such that both X and Y are independent sets, and all vertices of X are adjacent to those of Y. If both X,Y≠∅, then B is called proper. A biclique is a maximal proper complete bipartite set of a graph. When the requirement that X and Y are independent sets of G is dropped, we have a non-induced biclique. We show that it is NP-complete to test whether a subset of the vertices of a graph is part of a biclique. We propose an algorithm that generates all non-induced bicliques of a graph. In addition, we propose specialized efficient algorithms for generating the bicliques of special classes of graphs.     

There is no (95, 40, 12, 20) strongly regular graph

We show that there is no (95, 40, 12, 20) strongly regular graph and, consequently, there is no (96, 45, 24, 18) strongly regular graph, no nontrivial regular two‐graph on 96 vertices, and no partial geometry pg(4, 9, 2). The main idea of the result is based on the star complement technique and requires a moderate amount of computation.     

On the spanning connectivity of the generalized Petersen graphs P(n,3)

In this paper, we employed lattice model to describe the three internally vertex-disjoint paths that span the vertex set of the generalized Petersen graph $P(n,3)$. We showed that the $P(n,3)$ is 3-spanning connected for odd $n$. Based on the lattice model, five amalgamated and one extension mechanisms are introduced to recursively establish the 3-spanning connectivity of the $P(n,3)$. In each amalgamated mechanism, a particular lattice trail was amalgamated with the lattice trails that was dismembered, transferred, or extended from parts of the lattice trails for $P(n?6,3)$, where a lattice tail is a trail in the lattice model that represents a path in $P(n,3)$.     

On (s,t)-supereulerian graphs in locally highly connected graphs

Given two nonnegative integers s and t, a graph G is (s,t)-supereulerian if for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y|≤t, there is a spanning eulerian subgraph H of G that contains X and avoids Y. We prove that if G is connected and locally k-edge-connected, then G is (s,t)-supereulerian, for any pair of nonnegative integers s and t with s+t≤k−1. We further show that if s+t≤k and G is a connected, locally k-edge-connected graph, then for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y≤t, there is a spanning eulerian subgraph H that contains X and avoids Y, if and only if G−Y is not contractible to K₂ or to K_2,l with l odd.     

Domination of cyclic monotone (s, t)-graphs

The conjecture of zero domination of 0-cyclic monotone graphs is proved (anr-cyclic graph is a cyclic monotone (s, t)-graph exactlyr minimal paths of which have cycles). As a corollary, a formula for computing the reliability of an arbitrary 0-cyclic monotone graph is obtained. It is proved that the problem of determining the domination in the class ofr-cyclic monotone graphs is #P-complete for any fixed integerr≥1. Translated fromMatematicheskie Zametki, Vol. 67, No. 2, pp. 288–294, February, 2000.     

All cycle‐complete graph Ramsey numbers r(Cm,K6)

The cycle‐complete graph Ramsey number r(C_m, K_n) is the smallest integer N such that every graph G of order N contains a cycle C_m on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erd?s, Faudree, Rousseau and Schelp that r(C_m, K_n) = (m ? 1) (n ? 1) + 1 for all m ≥ n ≥ 3 (except r(C₃, K₃) = 6). This conjecture holds for 3 ≤ n ≤ 5. In this paper we will present a proof for n = 6 and for all n ≥ 7 with m ≥ n² ? 2n. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 251–260, 2003     

多机排序问题pm｜fix_j，pmtn｜C_（max）的多项式时间算法

在经典排序论中，一般都作以下两条假设：其一是每台机器在任一时刻至多加工一个零件，其二是每个零件在任一时刻至多被一台机器加工．在这篇文章中，研究多台机器可同时加工一个零件的多机排序问题，且每个零件可在固定的一个机器的子集上加工．本文在机器总数确定，零件加工可间断的条件下，设计出求这类问题最优解的计算方法，并研究了这种问题的计算复杂性．     

T-型树T(1,l,m)可由其谱唯一决定

一棵树称为T-型树,如果其恰有一个最大度为3的顶点.令T(l1,l2,l3)表示唯一的一棵T-型树,使得其3-度顶点到每个1-度顶点的距离分别为l1,l2,l3.本文证明T(1,l,m)(l,m≥1)可由其相邻谱唯一决定.     

A generalized quadrangle of order (s, t) with center of transitivity is an elation quadrangle if s ≤ t

We show that a generalized quadrangle of order (s, t) with a center of transitivity is an elation generalized quadrangle if s ≤ t. In order to obtain this result, we generalize Frohardt’s result on Kantor’s conjecture from elation quadrangles to the more general case of quadrangles with a center of transitivity.      

一类(a+1,3)型的距离正则图

设Γ是直径为d且型为(α 1,3)的距离正则图,其中α≥2.用l(c,a,b)表示交叉阵列l(Γ)中列(c,a,b)~t的个数,记r=r(Γ)=l(c_1,a_1,b_1),s=s(Γ)=l(c_(r 1),a(r 1),b_(r 1)).那末,若c_(r 1)=3且a_(r 1)=3a,则d=r s 1,c_d=4且Γ为正则拟2d边形.     

Wang’s B machines are efficiently universal,as is Hasenjaeger’s small universal electromechanical toy

In the 1960s Gisbert Hasenjaeger built Turing Machines from electromechanical relays and uniselectors. Recently, Glaschick reverse engineered the program of one of these machines and found that it is a universal Turing machine. In fact, its program uses only four states and two symbols, making it a very small universal Turing machine. (The machine has three tapes and a number of other features that are important to keep in mind when comparing it to other small universal machines.) Hasenjaeger’s machine simulates Hao Wang’s B machines, which were proved universal by Wang. Unfortunately, Wang’s original simulation algorithm suffers from an exponential slowdown when simulating Turing machines. Hence, via this simulation, Hasenjaeger’s machine also has an exponential slowdown when simulating Turing machines. In this work, we give a new efficient simulation algorithm for Wang’s B machines by showing that they simulate Turing machines with only a polynomial slowdown. As a second result, we find that Hasenjaeger’s machine also efficiently simulates Turing machines in polynomial time. Thus, Hasenjaeger’s machine is both small and fast. In another application of our result, we show that Hooper’s small universal Turing machine simulates Turing machines in polynomial time, an exponential improvement.     

On the number of (r,r+1)‐ factors in an (r,r+1)‐factorization of a simple graph

For integers d≥0, s≥0, a (d, d+s)‐graph is a graph in which the degrees of all the vertices lie in the set {d, d+1, …, d+s}. For an integer r≥0, an (r, r+1)‐factor of a graph G is a spanning (r, r+1)‐subgraph of G. An (r, r+1)‐factorization of a graph G is the expression of G as the edge‐disjoint union of (r, r+1)‐factors. For integers r, s≥0, t≥1, let f(r, s, t) be the smallest integer such that, for each integer d≥f(r, s, t), each simple (d, d+s) ‐graph has an (r, r+1) ‐factorization with x (r, r+1) ‐factors for at least t different values of x. In this note we evaluate f(r, s, t). © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 257‐268, 2009     

Vertex partitions of (C3,C4,C6)-free planar graphs

A graph is $(k_1,k_2)$-colorable if it admits a vertex partition into a graph with maximum degree at most $k_1$ and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete.     

Random intersection graphs when m=ω(n): An equivalence theorem relating the evolution of the G(n, m, p) and G(n, p) models

When the random intersection graph G(n, m, p) proposed by Karoński, Scheinerman, and Singer‐Cohen [Combin Probab Comput 8 (1999), 131–159] is compared with the independent‐edge G(n, p), the evolutions are different under some values of m and equivalent under others. In particular, when m=n^α and α>6, the total variation distance between the graph random variables has limit 0. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 156–176, 2000     

Corrigendum: The cover time of the giant component of a random graph,Random Structures and Algorithms 32 (2008), 401–439

The above paper gives an asymptotically precise estimate of the cover time of the giant component of a sparse random graph. The proof as it stands is not tight enough, and in particular, Eq. (64) is not strong enough to prove (65). The o(1) term in (64) needs to be improved to o(1/(lnn)²) for (65) to follow. The following section, which replaces Section 3.6, amends this oversight. The notation and definitions are from the paper. A further correction is needed. Property P2 claims that the conductance of the giant is whp , Ω(1/lnn). The proof of P2 in the appendix of the paper is not quite complete. A complete proof of Property P2 can be found in 1 , 2 . © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009