On the nullity of graphs with pendant trees

The nullity of a graph is defined as the multiplicity of the eigenvalue zero in the spectrum of the adjacency matrix of the graph. We investigate a class of graphs with pendant trees, and express the nullity of such graph in terms of that of its subgraphs. As an application of our results, we characterize unicyclic graphs with a given nullity.     

Partial Characterizations of Circular-Arc Graphs

A circular-arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular-arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to the following classes: diamond-free graphs, P₄-free graphs, paw-free graphs, and claw-free chordal graphs.     

Threshold functions for small subgraphs in simple graphs and multigraphs

We revisit the problem of counting the number of copies of a fixed graph in a random graph or multigraph, for various models of random (multi)graphs. For our proofs we introduce the notion of patchworks to describe the possible overlappings of copies of subgraphs. Furthermore, the proofs are based on analytic combinatorics to carry out asymptotic computations. The flexibility of our approach allows us to tackle a wide range of problems. We obtain the asymptotic number and the limiting distribution of the number of subgraphs which are isomorphic to a graph from a given set of graphs. The results apply to multigraphs as well as to (multi)graphs with degree constraints. One application is to scale-free multigraphs, where the degree distribution follows a power law, for which we show how to obtain the asymptotic number of copies of a given subgraph and give as an illustration the expected number of small cycles.     

Partial characterizations of circular‐arc graphs

A circular‐arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular‐arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to any of the following classes: P₄ ‐free graphs, paw‐free graphs, claw‐free chordal graphs and diamond‐free graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 289–306, 2009     

On maximum bipartite subgraphs

In this paper are investigated maximum bipartite subgraphs of graphs, i.e., bipartite subgraphs with a maximum number of edges. Such subgraphs are characterized and a criterion is given for a subgraph to be a unique maximum bipartite subgraph of a given graph. In particular maximum bipartite subgraphs of cubic graphs are investigated. It is shown that cubic graphs can be built up from five building stones (called elementary paths). Finally the investigation of a special class of cubic graphs yields a theorem which characterizes the Petersen graph and the dodecahedron graph by means of their maximum bipartite subgraphs.     

Partial characterizations of circle graphs

A circle graph is the intersection graph of a family of chords on a circle. There is no known characterization of circle graphs by forbidden induced subgraphs that do not involve the notions of local equivalence or pivoting operations. We characterize circle graphs by a list of minimal forbidden induced subgraphs when the graph belongs to one of the following classes: linear domino graphs, P₄-tidy graphs, and tree-cographs. We also completely characterize by minimal forbidden induced subgraphs the class of unit Helly circle graphs, which are those circle graphs having a model whose chords have all the same length, are pairwise different, and satisfy the Helly property.     

Constructably Laplacian integral graphs

A graph is Laplacian integral if the spectrum of its Laplacian matrix consists entirely of integers. We consider the class of constructably Laplacian integral graphs - those graphs that be constructed from an empty graph by adding a sequence of edges in such a way that each time a new edge is added, the resulting graph is Laplacian integral. We characterize the constructably Laplacian integral graphs in terms of certain forbidden vertex-induced subgraphs, and consider the number of nonisomorphic Laplacian integral graphs that can be constructed by adding a suitable edge to a constructably Laplacian integral graph. We also discuss the eigenvalues of constructably Laplacian integral graphs, and identify families of isospectral nonisomorphic graphs within the class.     

An adaptive,multiple restarts neural network algorithm for graph coloring

The graph coloring problem is amongst the most difficult ones in combinatorial optimization, with a diverse set of significant applications in science and industry. Previous neural network attempts at coloring graphs have not worked well. In particular, they do not scale up to large graphs. Furthermore, experimental evaluations on real-world graphs have been lacking, and so have comparisons with state of the art conventional algorithms. In this paper we address all of these issues. We develop an improved neural network algorithm for graph coloring that scales well with graph size. The algorithm employs multiple restarts, and adaptively reduces the network's size from restart as it learns bettwe ways to color a given graph. Hence it gets faster and leaner as it evolves. We evaluate this algorithm on a structurally diverse set of graphs that arise in different applications. We compare its performance with that of a state of the art conventional algorithm on identical graphs. The conventional algorithm works better overall, though ours is not far behind. Ours works better on some graphs. The inherent parallel and distributed nature of our algorithm, especially within a neural network architecture, is a potential advantage for implementation and speed up.     

Factorization of $$\mathbb {}$$-Valued Functions Induced by Graphs

In this paper, we study certain \(\mathbb {C}\)-valued functions induced by given graphs called graph zeta functions. In particular, we are interested in factorizations of such functions. We show that the factorizations of graph zeta functions are characterized by certain subgraphs of given graphs. Based on this factorization property on graph zeta functions, we define-and-study the non-factorizability of graphs.     

Bayesian selection of graphical regulatory models

We define a new class of coloured graphical models, called regulatory graphs. These graphs have their own distinctive formal semantics and can directly represent typical qualitative hypotheses about regulatory processes like those described by various biological mechanisms. They admit an embellishment into classes of probabilistic statistical models and so standard Bayesian methods of model selection can be used to choose promising candidate explanations of regulation. Regulation is modelled by the existence of a deterministic relationship between the longitudinal series of observations labelled by the receiving vertex and the donating one. This class contains longitudinal cluster models as a degenerate graph. Edge colours directly distinguish important features of the mechanism like inhibition and excitation and graphs are often cyclic. With appropriate distributional assumptions, because the regulatory relationships map onto each other through a group structure, it is possible to define a conditional conjugate analysis. This means that even when the model space is huge it is nevertheless feasible, using a Bayesian MAP search, to a discover regulatory network with a high Bayes Factor score. We also show that, like the class of Bayesian Networks, regulatory graphs also admit a formal but distinctive causal algebra. The topology of the graph then represents collections of hypotheses about the predicted effect of controlling the process by tearing out message passers or forcing them to transmit certain signals. We illustrate our methods on a microarray experiment measuring the expression of thousands of genes as a longitudinal series where the scientific interest lies in the circadian regulation of these plants.     

Polar cographs

Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s,k)-polar if there exists a partition A,B of its vertex set such that A induces a complete s-partite graph (i.e., a collection of at most s disjoint stable sets with complete links between all sets) and B a disjoint union of at most k cliques (i.e., the complement of a complete k-partite graph).Recognizing a polar graph is known to be NP-complete. These graphs have not been extensively studied and no good characterization is known. Here we consider the class of polar graphs which are also cographs (graphs without induced path on four vertices). We provide a characterization in terms of forbidden subgraphs. Besides, we give an algorithm in time O(n) for finding a largest induced polar subgraph in cographs; this also serves as a polar cograph recognition algorithm. We examine also the monopolar cographs which are the (s,k)-polar cographs where min(s,k)?1. A characterization of these graphs by forbidden subgraphs is given. Some open questions related to polarity are discussed.     

Monochromatic and Heterochromatic Subgraphs in Edge-Colored Graphs - A Survey

Nowadays the term monochromatic and heterochromatic (or rainbow, multicolored) subgraphs of an edge-colored graph appeared frequently in literature, and many results on this topic have been obtained. In this paper, we survey results on this subject. We classify the results into the following categories: vertex-partitions by monochromatic subgraphs, such as cycles, paths, trees; vertex partition by some kinds of heterochromatic subgraphs; the computational complexity of these partition problems; some kinds of large monochromatic and heterochromatic subgraphs. We have to point out that there are a lot of results on Ramsey type problem of monochromatic and heterochromatic subgraphs. However, it is not our purpose to include them in this survey because this is slightly different from our topics and also contains too large amount of results to deal with together. There are also some interesting results on vertex-colored graphs, but we do not include them, either. Supported by NSFC, PCSIRT and the “973” program.     

Computational Statistical Methods for Social Network Models

We review the broad range of recent statistical work in social network models, with emphasis on computational aspects of these methods. Particular focus is applied to exponential-family random graph models (ERGM) and latent variable models for data on complete networks observed at a single time point, though we also briefly review many methods for incompletely observed networks and networks observed at multiple time points. Although we mention far more modeling techniques than we can possibly cover in depth, we provide numerous citations to current literature. We illustrate several of the methods on a small, well-known network dataset, Sampson's monks, providing code where possible so that these analyses may be duplicated.     

The graph reconstruction number

The reconstruction number of graph G is the minimum number of point-deleted subgraphs required in order to uniquely identify the original graph G. We list, based on computer calculations, the reconstruction number for all graphs with at most seven points. Some constructions and conjectures for graphs of higher order are given. the most striking statement is our concluding conjeture that almost all graphs have have reconstruction number three.     

On small graphs critical with respect to edge colourings

A simple graph is said to be of class 1 or of class 2 according as its chromatic index equals the maximum degree or is one greater. A graph of class 2 is called critical if all its proper subgraphs have smaller chromatic index. It has been conjectured by Beineke and Wilson and by Jakobsen that all critical graphs have odd order. In this paper we verify the truth of this conjecture for all graphs of order less than 12 and all graphs of order 12 and maximum degree 3. We also determine all critical graphs through order 7.     

A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing

We generalize Dijkstra's algorithm for finding shortest paths in digraphs with non-negative integral edge lengths. Instead of labeling individual vertices we label subgraphs which partition the given graph. We can achieve much better running times if the number of involved subgraphs is small compared to the order of the original graph and the shortest path problems restricted to these subgraphs is computationally easy.As an application we consider the VLSI routing problem, where we need to find millions of shortest paths in partial grid graphs with billions of vertices. Here, our algorithm can be applied twice, once in a coarse abstraction (where the labeled subgraphs are rectangles), and once in a detailed model (where the labeled subgraphs are intervals). Using the result of the first algorithm to speed up the second one via goal-oriented techniques leads to considerably reduced running time. We illustrate this with a state-of-the-art routing tool on leading-edge industrial chips.     

Triangle-free strongly circular-perfect graphs

Zhu [X. Zhu, Circular-perfect graphs, J. Graph Theory 48 (2005) 186-209] introduced circular-perfect graphs as a superclass of the well-known perfect graphs and as an important χ-bound class of graphs with the smallest non-trivial χ-binding function χ(G)≤ω(G)+1. Perfect graphs have been recently characterized as those graphs without odd holes and odd antiholes as induced subgraphs [M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, Ann. Math. (in press)]; in particular, perfect graphs are closed under complementation [L. Lovász, Normal hypergraphs and the weak perfect graph conjecture, Discrete Math. 2 (1972) 253-267]. To the contrary, circular-perfect graphs are not closed under complementation and the list of forbidden subgraphs is unknown.We study strongly circular-perfect graphs: a circular-perfect graph is strongly circular-perfect if its complement is circular-perfect as well. This subclass entails perfect graphs, odd holes, and odd antiholes. As the main result, we fully characterize the triangle-free strongly circular-perfect graphs, and prove that, for this graph class, both the stable set problem and the recognition problem can be solved in polynomial time.Moreover, we address the characterization of strongly circular-perfect graphs by means of forbidden subgraphs. Results from [A. Pêcher, A. Wagler, On classes of minimal circular-imperfect graphs, Discrete Math. (in press)] suggest that formulating a corresponding conjecture for circular-perfect graphs is difficult; it is even unknown which triangle-free graphs are minimal circular-imperfect. We present the complete list of all triangle-free minimal not strongly circular-perfect graphs.     

Hereditary Efficiently Dominatable Graphs

An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the graph's vertex set. We introduce graphs that are hereditary efficiently dominatable in that sense that every induced subgraph of the graph contains an efficient dominating set. We prove a decomposition theorem for (bull, fork, C₄)‐free graphs, based on which we characterize, in terms of forbidden induced subgraphs, the class of hereditary efficiently dominatable graphs. We also give a decomposition theorem for hereditary efficiently dominatable graphs and examine some algorithmic aspects of such graphs. In particular, we give a polynomial time algorithm for finding an efficient dominating set (if one exists) in a class of graphs properly containing the class of hereditary efficiently dominatable graphs by reducing the problem to the maximum weight independent set problem in claw‐free graphs.     

Weak reconstruction of strong product graphs

We prove that the class of nontrivial connected strong product graphs is weakly reconstructible. We also show that any nontrivial connected thin strong product graph can be uniquely reconstructed from each of its one-vertex-deleted deleted subgraphs.     

Highly Symmetric Subgraphs of Hypercubes

Two questions are considered, namely (i) How many colors are needed for a coloring of the n-cube without monochromatic quadrangles or hexagons? We show that four colors suffice and thereby settle a problem of Erdös. (ii) Which vertex-transitive induced subgraphs does a hypercube have? An interesting graph has come up in this context: If we delete a Hamming code from the 7-cube, the resulting graph is 6-regular, vertex-transitive and its edges can be two-colored such that the two monochromatic subgraphs are isomorphic, cubic, edge-transitive, nonvertex-transitive graphs of girth 10.