An algorithm for determining the automorphism partitioning of an undirected graph

An Algol 60 program for determining the automorphism partitioning of an undirected unlabelled graph is presented. For graphs that do not contain strongly regular subgraphs, the time is at worstO(n ⁴) wheren is the number of vertices in the graph. The algorithm is based on the Corneil-Gotlieb conjecture.     

An exact algorithm for the maximum k-club problem in an undirected graph

In this paper, we prove that the maximum k-club problem (MkCP) defined on an undirected graph is NP-hard. We also give an integer programming formulation for this problem as well as an exact branch-and-bound algorithm and computational results on instances involving up to 200 vertices. Instances defined on very dense graphs can be solved to optimality within insignificant computing times. When k=2, the most difficult cases appear to be those where the graph density is around 0.15.     

Improved algorithms for the random cluster graph model

We model noisy clustering data using random graphs: Clusters correspond to disjoint sets of vertices. Two vertices from the same set (resp., different sets) share an edge with probability p (resp., r < p). We give algorithms that reconstruct the clusters from the graph with high probability. Compared to previous studies, our algorithms have lower time complexity and apply under wider parameter range. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Finding fixed-length circuits and cycles in undirected edge-weighted graphs: an application with street networks

Journal of Heuristics - This paper proposes two heuristic algorithms for finding fixed-length circuits and cycles in undirected edge-weighted graphs. It focusses particularly on a largely...     

Large non-planar graphs and an application to crossing-critical graphs

We prove that, for every positive integer k, there is an integer N such that every 4-connected non-planar graph with at least N vertices has a minor isomorphic to K4,k, the graph obtained from a cycle of length 2k+1 by adding an edge joining every pair of vertices at distance exactly k, or the graph obtained from a cycle of length k by adding two vertices adjacent to each other and to every vertex on the cycle. We also prove a version of this for subdivisions rather than minors, and relax the connectivity to allow 3-cuts with one side planar and of bounded size. We deduce that for every integer k there are only finitely many 3-connected 2-crossing-critical graphs with no subdivision isomorphic to the graph obtained from a cycle of length 2k by joining all pairs of diagonally opposite vertices.     

Spectral graph features for the classification of graphs and graph sequences

In this paper, the classification power of the eigenvalues of six graph-associated matrices is investigated. Each matrix contains a certain type of geometric/ spatial information, which may be important for the classification process. The performances of the different feature types is evaluated on two data sets: first a benchmark data set for optical character recognition, where the extracted eigenvalues were utilized as feature vectors for multi-class classification using support vector machines. Classification results are presented for all six feature types, as well as for classifier combinations at decision level. For the decision level combination, probabilistic output support vector machines have been applied, with a performance up to 92.4 %. To investigate the power of the spectra for time dependent tasks, too, a second data set was investigated, consisting of human activities in video streams. To model the time dependency, hidden Markov models were utilized and the classification rate reached 98.3 %.     

On a class of polynomials obtained from the circuits in a graph and its application to characteristics polynomials of graphs

Let G be a graph. With each circuit α in G, we can associate a weight w_α, A circuit cover of G is a spanning subgraph of G in which every component is a circuit. With every circuit cover of G, we can associate the monomial Π_αw_α, where the product is taken over all components of the cover. The circuit polynomial of G is ΣΠ_αw_α, where the summation is taken over all circuit covers in G. We show that the characteristics polynomial of G is a special case of its circuit polynomial. Previously obtained and also new results for characteristic polynomials are easily deduced. We also derive the circuit polynomials of various classes of graphs.     

The number of graphs and a random graph with a given degree sequence

We consider the set of all graphs on n labeled vertices with prescribed degrees D = (d₁,…,d_n). For a wide class of tame degree sequences D we obtain a computationally efficient asymptotic formula approximating the number of graphs within a relative error which approaches 0 as n grows. As a corollary, we prove that the structure of a random graph with a given tame degree sequence D is well described by a certain maximum entropy matrix computed from D. We also establish an asymptotic formula for the number of bipartite graphs with prescribed degrees of vertices, or, equivalently, for the number of 0‐1 matrices with prescribed row and column sums. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Strong sufficient conditions for the existence of Hamiltonian circuits in undirected graphs

In this paper, we derive some results giving sufficient conditions for a graph G containing a Hamiltonian path to be Hamiltonian. In particular the Bondy-Chvátal theorem [J. A. Bondy and V. Chvátal, Discrete Math. 15 (1976), 111–135] is derived as a corollary of the main theorem of this paper and hence a more powerful closure operation than the one introduced by Bondy and Chvátal is defined. These results can be viewed as a step towards a unification of the various known results on the existence of Hamiltonian circuits in undirected graphs. Moreover, Theorem 1 of this paper provides a counterpart of the Chvátal-Erdös theorem [V. Chvátal and P. Erdös, Discrete Math. 2 (1972), 111–113] which gives a sufficient condition for a Hamiltonian circuit in terms of global vertex connectivity and independence number.     

Harnack inequalities on weighted graphs and some applications to the random conductance model

We establish elliptic and parabolic Harnack inequalities on graphs with unbounded weights. As an application we prove a local limit theorem for a continuous time random walk \(X\) in an environment of ergodic random conductances taking values in \((0, \infty )\) satisfying some moment conditions.     

A Fourier formulation of the Frostman criterion for random graphs and its applications to wavelet series

In the paper by F. Roueff “Almost sure Hausdorff dimensions of graphs of random wavelet series” [J. Fourier Anal. Appl., to appear] lower bounds of the Hausdorff dimension of the graphs of random wavelet series (RWS) have been obtained essentially under the hypothesis that the wavelet coefficients have a bounded probability density function (p.d.f.) with respect to the Lebesgue measure. In this article we extend these lower bounds to classes of RWS that do not satisfy this hypothesis.     

On a relation between the domination number and a strongly connected bidirection of an undirected graph

As a generalization of directed and undirected graphs, Edmonds and Johnson [J. Edmonds, E.L. Johnson, Matching: A well-solved class of linear programs, in: R. Guy, H. Hanani, N. Sauer, J. Schönheim (Eds.), Combinatorial Structures and their Applications, Gordon and Breach, New York, 1970, pp. 88-92] introduced bidirected graphs. A bidirected graph is a graph each arc of which has either two positive end-vertices (tails), two negative end-vertices (heads), or one positive end-vertex (tail) and one negative end-vertex (head). We extend the notion of directed paths, distance, diameter and strong connectivity from directed to bidirected graphs and characterize those undirected graphs that allow a strongly connected bidirection. Considering the problem of finding the minimum diameter of all strongly connected bidirections of a given undirected graph, we generalize a result of Fomin et al. [F.V. Fomin, M. Matamala, E. Prisner, I. Rapaport, Bilateral orientations in graphs: Domination and AT-free classes, in: Proceedings of the Brazilian Symposium on Graphs, Algorithms and Combinatorics, GRACO 2001, in: Electronics Notes in Discrete Mathematics, vol. 7, Elsevier Science Publishers, 2001] about directed graphs and obtain an upper bound for the minimum diameter which depends on the minimum size of a dominating set and the number of bridges in the undirected graph.     

On the sizes of graphs and their powers: The undirected case

Let G be an undirected graph and G^r be its r-th power. We study different issues dealing with the number of edges in G and G^r. In particular, we answer the following question: given an integer r≥2 and all connected graphs G of order n such that G^r≠K_n, what is the minimum number of edges that are added when going from G to G^r, and which are the graphs achieving this bound?     

A latent process model for time series of attributed random graphs

We introduce a latent process model for time series of attributed random graphs for characterizing multiple modes of association among a collection of actors over time. Two mathematically tractable approximations are derived, and we examine the performance of a class of test statistics for an illustrative change-point detection problem and demonstrate that the analysis through approximation can provide valuable information regarding inference properties.     

图的区间边着色的收缩图方法

图G的一个用了颜色1,2,…,t的边着色称为区间t-着色,如果所有t种颜色都被用到,并且关联于G的同一个顶点的边上的颜色是各不相同的,且这些颜色构成了一个连续的整数区间.G称作是可区间着色的,如果对某个正整数t,G有一个区间t-着色.所有可区间着色的图构成的集合记作■.对图G∈■,使得G有一个区间t-着色的t的最小值和最大值分别记作ω(G)和W(G).现给出了图的区间着色的收缩图方法.利用此方法,我们对双圈图G∈■,证明了ω(G)=△(G)或△(G)+1,并且完全确定了ω(G)=△(G)及ω(G)=△(G)+1的双圈图类.     

Rank one perturbation and its application to the laplacian spectrum of a graph

Characterization of rank one perturbations of symmetric matrices which change only one eigenvalue are given. Then the result is applied to study how the Laplacian spectrum of a graph changes when adding an edge.     

EM algorithm and its application to testing hypotheses

The conventional method for testing hypotheses is to find an exact or asymptotic distributionof a test statistic But when the model is complex and the sample size is small,difficulty often arises. Thispaper aims to present a method for finding maximum probability with the help of EM algorithm. For any fixedsample size,this method can be used not only to obtain an accurate test but also to check the real level of     

NSD序列加权和的中心极限定理及其在EV回归模型中的应用

基于负超可加相依(简称为NSD)随机序列的性质及其一些不等式,利用随机变量的截断方法建立了NSD随机序列加权和的中心极限定理,从而推广了负相协NA随机序列的相应结论.并将其应用到变系数EV回归模型,得到了未知参数LS估计的渐近正态性.     

Law of the iterated logarithm for random graphs

A milestone in probability theory is the law of the iterated logarithm (LIL), proved by Khinchin and independently by Kolmogorov in the 1920s, which asserts that for iid random variables with mean 0 and variance 1 In this paper we prove that LIL holds for various functionals of random graphs and hypergraphs models. We first prove LIL for the number of copies of a fixed subgraph H. Two harder results concern the number of global objects: perfect matchings and Hamiltonian cycles. The main new ingredient in these results is a large deviation bound, which may be of independent interest. For random k‐uniform hypergraphs, we obtain the Central Limit Theorem and LIL for the number of Hamilton cycles.     

Radial basis approximation and its application to biharmonic equation

Order of approximating functions and their derivatives by radial bases on arbitrarily scattered data is derived. And then radial bases are used to construct solutions of biharmonic equations that approximate potential integrals for the exact solutions with the order of approximation derived.