Competing first passage percolation on random graphs with finite variance degrees

We study the growth of two competing infection types on graphs generated by the configuration model with a given degree sequence. Starting from two vertices chosen uniformly at random, the infection types spread via the edges in the graph in that an uninfected vertex becomes type 1 (2) infected at rate λ₁ (λ₂) times the number of nearest neighbors of type 1 (2). Assuming (essentially) that the degree of a randomly chosen vertex has finite second moment, we show that if λ₁ = λ₂, then the fraction of vertices that are ultimately infected by type 1 converges to a continuous random variable V ∈ (0,1), as the number of vertices tends to infinity. Both infection types hence occupy a positive (random) fraction of the vertices. If λ₁ ≠ λ₂, on the other hand, then the type with the larger intensity occupies all but a vanishing fraction of the vertices. Our results apply also to a uniformly chosen simple graph with the given degree sequence.     

完全$r$部图乘积上的Graham猜想

图G的Pebbling数f(G)是最小的正整数n,使得不论n个Pebble如何放置在G的顶点上,总可以通过一系列的Pebbling移动把1个Pebble移到任意一点上,其中Pebbling移动是从一个顶点处移走两个Pebble而把其中一个移到与其相邻的一个顶点上.Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H).本文证明对于一个完全γ部图和一个具有2-Pebbleing性质的图来说,Graham猜想成立.作为一个推论,当G和H均为完全γ部图时,Graham猜想成立.     

A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem

In this paper, a particle swarm optimization algorithm (PSO) is presented to solve the permutation flowshop sequencing problem (PFSP) with the objectives of minimizing makespan and the total flowtime of jobs. For this purpose, a heuristic rule called the smallest position value (SPV) borrowed from the random key representation of Bean [J.C. Bean, Genetic algorithm and random keys for sequencing and optimization, ORSA Journal of Computing 6(2) (1994) 154–160] was developed to enable the continuous particle swarm optimization algorithm to be applied to all classes of sequencing problems. In addition, a very efficient local search, called variable neighborhood search (VNS), was embedded in the PSO algorithm to solve the well known benchmark suites in the literature. The PSO algorithm was applied to both the 90 benchmark instances provided by Taillard [E. Taillard, Benchmarks for basic scheduling problems, European Journal of Operational Research, 64 (1993) 278–285], and the 14,000 random, narrow random and structured benchmark instances provided by Watson et al. [J.P. Watson, L. Barbulescu, L.D. Whitley, A.E. Howe, Contrasting structured and random permutation flowshop scheduling problems: Search space topology and algorithm performance, ORSA Journal of Computing 14(2) (2002) 98–123]. For makespan criterion, the solution quality was evaluated according to the best known solutions provided either by Taillard, or Watson et al. The total flowtime criterion was evaluated with the best known solutions provided by Liu and Reeves [J. Liu, C.R. Reeves, Constructive and composite heuristic solutions to the P∥∑C_i scheduling problem, European Journal of Operational Research 132 (2001) 439–452], and Rajendran and Ziegler [C. Rajendran, H. Ziegler, Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs, European Journal of Operational Research, 155(2) (2004) 426–438]. For the total flowtime criterion, 57 out of the 90 best known solutions reported by Liu and Reeves, and Rajendran and Ziegler were improved whereas for the makespan criterion, 195 out of the 800 best known solutions for the random and narrow random problems reported by Watson et al. were improved by the VNS version of the PSO algorithm.     

Distance-hereditary graphs are clique-perfect

In this paper, we show that the clique-transversal number τ_C(G) and the clique-independence number α_C(G) are equal for any distance-hereditary graph G. As a byproduct of proving that τ_C(G)=α_C(G), we give a linear-time algorithm to find a minimum clique-transversal set and a maximum clique-independent set simultaneously for distance-hereditary graphs.     

Characterizing distance-regularity of graphs by the spectrum

We characterize the distance-regular Ivanov-Ivanov-Faradjev graph from the spectrum, and construct cospectral graphs of the Johnson graphs, Doubled Odd graphs, Grassmann graphs, Doubled Grassmann graphs, antipodal covers of complete bipartite graphs, and many of the Taylor graphs. We survey the known results on cospectral graphs of the Hamming graphs, and of all distance-regular graphs on at most 70 vertices.     

STABILITY NUMBER IN SUBCLASSES OF P_5~-FREE GRAPHS

§1　IntroductionLet Pn,Cn,and Kn be the path,the cycle,and the complete graph of order n,respectively.The complete bipartite graph with cardinalities ofparts m and n is denoted byKm,n.Disjoint union of n copies of a graph G is denoted by n G;Gis the complement of agraph G.A setof pairwise non-adjacent vertices in a graph is called stable.A maximum stableset of a graph G has the largest cardinalityα( G) among all stable sets of G;α( G) is calledthe stability number of G.Let Z be a s…     

Coincidence theorem for the direct correlation function of hard-particle fluids

The Mayerf-function for purely hard particles of arbitrary shape satisfiesf ²(1, 2)=–f(1, 2). This relation can be introduced into the graphical expansion of the direct correlation functionc(1, 2) to obtain a graphical expression for the case of exact coincidence, in position and orientation, of two identical hard cores. The resulting expression forc(1, 1)+1 contains only graphsG fromc(1), the sum of irreducible graphs with one labeled point. Relative to its coefficient inc(1),G occurs inc(1, 1) with an additional factorR _c which is 1 for the leading graph in the expansion and of the form 2–2L(G) for all other graphs. HereL(G)=0, 1, 2,..., is a nonnegative integer. Topological analysis is used to derive an expression forL(G) in terms of the connectivity properties ofG.     

On the maximum number of edges in quasi-planar graphs

A topological graph is quasi-planar, if it does not contain three pairwise crossing edges. Agarwal et al. [P.K. Agarwal, B. Aronov, J. Pach, R. Pollack, M. Sharir, Quasi-planar graphs have a linear number of edges, Combinatorica 17 (1) (1997) 1-9] proved that these graphs have a linear number of edges. We give a simple proof for this fact that yields the better upper bound of 8n edges for n vertices. Our best construction with 7n−O(1) edges comes very close to this bound. Moreover, we show matching upper and lower bounds for several relaxations and restrictions of this problem. In particular, we show that the maximum number of edges of a simple quasi-planar topological graph (i.e., every pair of edges have at most one point in common) is 6.5n−O(1), thereby exhibiting that non-simple quasi-planar graphs may have many more edges than simple ones.     

Latin bitrades derived from groups

A Latin bitrade is a pair of partial Latin squares which are disjoint, occupy the same set of non-empty cells, and whose corresponding rows and columns contain the same set of entries. In [A. Drápal, On geometrical structure and construction of Latin trades, Advances in Geometry (in press)] it is shown that a Latin bitrade may be thought of as three derangements of the same set, whose product is the identity and whose cycles pairwise have at most one point in common. By letting a group act on itself by right translation, we show how some Latin bitrades may be derived directly from groups. Properties of Latin bitrades such as homogeneity, minimality (via thinness) and orthogonality may also be encoded succinctly within the group structure. We apply the construction to some well-known groups, constructing previously unknown Latin bitrades. In particular, we show the existence of minimal, k-homogeneous Latin bitrades for each odd k≥3. In some cases these are the smallest known such examples.     

Chaotic Numbers of Complete Bipartite Graphs and Tripartite Graphs

In this paper, we study the chaotic numbers of complete bipartite graphs and complete tripartite graphs. For the complete bipartite graphs, we find closed-form formulas of the chaotic numbers and characterize all chaotic mappings. For the complete tripartite graphs, we develop an algorithm running in O(n ⁴ ₃) time to find the chaotic numbers, with n ₃ the number of vertices in the largest partite set.Research supported by NSC 90-2115-M-036-003.The author thanks the authors of Ref. 6, since his work was motivated by their work. Also, the author thanks the referees for helpful comments which made the paper more readable.