Preperfect graphs

We say that a vertexx of a graph is predominant if there exists another vertexy ofG such that either every maximum clique ofG containingy containsx or every maximum stable set containingx containsy. A graph is then called preperfect if every induced subgraph has a predominant vertex. We show that preperfect graphs are perfect, and that several well-known classes of perfect graphs are preperfect. We also derive a new characterization of perfect graphs.     

RandomlyH-coverable graphs

A graph israndomly matchable if every matching of the graph is contained in a perfect matching. We generalize this notion and say that a graphG israndomly H-coverable if every set of independent subgraphs, each isomorphic toH, that does not cover the vertices ofG can be extended to a larger set of independent copies ofH. Various problems are considered for the situation whereH is a path. In particular, we characterize the graphs that are randomlyP ₃ -coverable.     

Codes And Xor Graph Products

What is the maximum possible number, f₃(n), of vectors of length n over {0,1,2} such that the Hamming distance between every two is even? What is the maximum possible number, g³(n), of vectors in {0,1,2}ⁿ such that the Hamming distance between every two is odd? We investigate these questions, and more general ones, by studying Xor powers of graphs, focusing on their independence number and clique number, and by introducing two new parameters of a graph G. Both parameters denote limits of series of either clique numbers or independence numbers of the Xor powers of G (normalized appropriately), and while both limits exist, one of the series grows exponentially as the power tends to infinity, while the other grows linearly. As a special case, it follows that f₃(n) = Θ(2ⁿ) whereas g₃(n)=Θ(n). * Research supported in part by a USA-Israeli BSF grant, by the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. † Research partially supported by a Charles Clore Foundation Fellowship.     

Solution to a problem of C. D. Godsil regarding bipartite graphs with unique perfect matching

We give the solution to the following question of C. D. Godsil[2]: Among the bipartite graphsG with a unique perfect matching and such that a bipartite graph obtains when the edges of the matching are contracted, characterize those having the property thatG ⁺G, whereG ⁺ is the bipartite multigraph whose adjacency matrix,B ⁺, is diagonally similar to the inverse of the adjacency matrix ofG put in lower-triangular form. The characterization is thatG must be obtainable from a bipartite graph by adding, to each vertex, a neighbor of degree one. Our approach relies on the association of a directed graph to each pair (G, M) of a bipartite graphG and a perfect matchingM ofG.     

Graph colourings with forbidden k-coloured subgraphs

Abstract

For a set F of graphs and a natural number k, an (F, k)-colouring of a graph G is a proper colouring of V (G) such that no subgraph of G isomorphic to an element of F is coloured with at most k colours. Equivalently, if P is the class of all graphs that do not contain an element of F as a subgraph, a χP,k colouring of G is a proper colouring such that the union of at most k colour classes induces a graph in P. The smallest number of colours in such a colouring of G, if it exists, is denoted by χP,k (G). We give some general results on χP,k-colourings and investigate values of χP,k (G) for some choices of P and classes of graphs G.     

Maximum nullity of outerplanar graphs and the path cover number

Let G=(V,E) be a graph with V={1,2,…,n}. Define S(G) as the set of all n×n real-valued symmetric matrices A=[a_ij] with a_ij≠0,i≠j if and only if ij∈E. By M(G) we denote the largest possible nullity of any matrix A∈S(G). The path cover number of a graph G, denoted P(G), is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G.There has been some success with relating the path cover number of a graph to its maximum nullity. Johnson and Duarte [5], have shown that for a tree T,M(T)=P(T). Barioli et al. [2], show that for a unicyclic graph G,M(G)=P(G) or M(G)=P(G)-1. Notice that both families of graphs are outerplanar. We show that for any outerplanar graph G,M(G)?P(G). Further we show that for any partial 2-path G,M(G)=P(G).     

On kernels in perfect graphs

A kernel of a digraphD is a set of vertices which is both independent and absorbant. In 1983, C. Berge and P. Duchet conjectured that an undirected graphG is perfect if and only if the following condition is fulfilled: ifD is an orientation ofG (where pairs of opposite arcs are allowed) and if every clique ofD has a kernel thenD has a kernel. We prove here the conjecture for the complements of strongly perfect graphs and establish that a minimal counterexample to the conjecture is not a complete join of an independent set with another graph.     

The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample

Let G be an undirected graph on n vertices and let S(G) be the set of all real symmetric n×n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The inverse inertia problem for G asks which inertias can be attained by a matrix in S(G). We give a complete answer to this question for trees in terms of a new family of graph parameters, the maximal disconnection numbers of a graph. We also give a formula for the inertia set of a graph with a cut vertex in terms of inertia sets of proper subgraphs. Finally, we give an example of a graph that is not inertia-balanced, which settles an open problem from the October 2006 AIM Workshop on Spectra of Families of Matrices described by Graphs, Digraphs and Sign Patterns. We also determine some restrictions on the inertia set of any graph.     

On entropy-preserving stochastic averages

When an n×n doubly stochastic matrix A acts on Rⁿ on the left as a linear transformation and P is an n-long probability vector, we refer to the new probability vector AP as the stochastic average of the pair (A,P). Let Γ_n denote the set of pairs (A,P) whose stochastic average preserves the entropy of P:H(AP)=H(P). Γ_n is a subset of B_n×Σ_n where B_n is the Birkhoff polytope and Σ_n is the probability simplex.We characterize Γ_n and determine its geometry, topology,and combinatorial structure. For example, we find that (A,P)∈Γ_n if and only if A^tAP=P. We show that for any n, Γ_n is a connected set, and is in fact piecewise-linearly contractible in B_n×Σ_n. We write Γ_n as a finite union of product subspaces, in two distinct ways. We derive the geometry of the fibers (A,·) and (·,P) of Γ_n. Γ₃ is worked out in detail. Our analysis exploits the convexity of xlogx and the structure of an efficiently computable bipartite graph that we associate to each ds-matrix. This graph also lets us represent such a matrix in a permutation-equivalent, block diagonal form where each block is doubly stochastic and fully indecomposable.     

Energy of line graphs

The energy of a graph is equal to the sum of the absolute values of its eigenvalues. The energy of a matrix is equal to the sum of its singular values. We establish relations between the energy of the line graph of a graph G and the energies associated with the Laplacian and signless Laplacian matrices of G.     

Drawing 4-Pfaffian graphs on the torus

We say that a graph G is k-Pfaffian if the generating function of its perfect matchings can be expressed as a linear combination of Pfaffians of k matrices corresponding to orientations of G. We prove that 3-Pfaffian graphs are 1-Pfaffian, 5-Pfaffian graphs are 4-Pfaffian and that a graph is 4-Pfaffian if and only if it can be drawn on the torus (possibly with crossings) so that every perfect matching intersects itself an even number of times. We state conjectures and prove partial results for k>5. The author was supported in part by NSF under Grant No. DMS-0200595 and DMS-0701033.     

Zeta functions of line, middle, total graphs of a graph and their coverings

We consider the (Ihara) zeta functions of line graphs, middle graphs and total graphs of a regular graph and their (regular or irregular) covering graphs. Let L(G), M(G) and T(G) denote the line, middle and total graph of G, respectively. We show that the line, middle and total graph of a (regular and irregular, respectively) covering of a graph G is a (regular and irregular, respectively) covering of L(G), M(G) and T(G), respectively. For a regular graph G, we express the zeta functions of the line, middle and total graph of any (regular or irregular) covering of G in terms of the characteristic polynomial of the covering. Also, the complexities of the line, middle and total graph of any (regular or irregular) covering of G are computed. Furthermore, we discuss the L-functions of the line, middle and total graph of a regular graph G.     

On the reduced signless Laplacian spectrum of a degree maximal graph

For a (simple) graph G, the signless Laplacian of G is the matrix A(G)+D(G), where A(G) is the adjacency matrix and D(G) is the diagonal matrix of vertex degrees of G; the reduced signless Laplacian of G is the matrix Δ(G)+B(G), where B(G) is the reduced adjacency matrix of G and Δ(G) is the diagonal matrix whose diagonal entries are the common degrees for vertices belonging to the same neighborhood equivalence class of G. A graph is said to be (degree) maximal if it is connected and its degree sequence is not majorized by the degree sequence of any other connected graph. For a maximal graph, we obtain a formula for the characteristic polynomial of its reduced signless Laplacian and use the formula to derive a localization result for its reduced signless Laplacian eigenvalues, and to compare the signless Laplacian spectral radii of two well-known maximal graphs. We also obtain a necessary condition for a maximal graph to have maximal signless Laplacian spectral radius among all connected graphs with given numbers of vertices and edges.     

Total Colorings Of Degenerate Graphs

A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, such that no two adjacent or incident elements receive the same color. A graph G is s-degenerate for a positive integer s if G can be reduced to a trivial graph by successive removal of vertices with degree ≤s. We prove that an s-degenerate graph G has a total coloring with Δ+1 colors if the maximum degree Δ of G is sufficiently large, say Δ≥4s+3. Our proof yields an efficient algorithm to find such a total coloring. We also give a lineartime algorithm to find a total coloring of a graph G with the minimum number of colors if G is a partial k-tree, that is, the tree-width of G is bounded by a fixed integer k.     

Ordering n-vertex cacti with matching number q by their spectral radii

Abstract

A connected graph G is a cactus if any two of its cycles have at most one common vertex. Denote by the set of n-vertex cacti with matching number q. Huang, Deng and Simi? [23] identified the unique graph with the maximum spectral radius among 2q-vertex cacti with perfect matchings. In this paper, as a continuance of it, the largest and second largest spectral radii together with the corresponding graphs among are determined. Consequently, the first two largest spectral radii together with cacti having perfect matchings are also determined.     

On a Problem of Cameron’s on Inexhaustible Graphs

A graph G is inexhaustible if whenever a vertex of G is deleted the remaining graph is isomorphic to G. We address a question of Cameron [6], who asked which countable graphs are inexhaustible. In particular, we prove that there are continuum many countable inexhaustible graphs with properties in common with the infinite random graph, including adjacency properties and universality. Locally finite inexhaustible graphs and forests are investigated, as is a semigroup structure on the class of inexhaustible graphs. We extend a result of [7] on homogeneous inexhaustible graphs to pseudo-homogeneous inexhaustible graphs.The authors gratefully acknowledge support from the Natural Science and Engineering Research Council of Canada (NSERC).     

Characteristic polynomial of a generalized complete product of matrices

For a simple graph G, let denote the complement of G relative to the complete graph and let P_G(x)=det(xI-A(G)) where A(G) denotes the adjacency matrix of G. The complete product G∇H of two simple graphs G and H is the graph obtained from G and H by joining every vertex of G to every vertex of H. In [2]P_G∇H(x) is represented in terms of P_G, , P_H and . In this paper we extend the notion of complete product of simple graphs to that of generalized complete product of matrices and obtain their characteristic polynomials.     

Matching behaviour is asymptotically normal

Ak-matching in a graphG is a set ofk edges, no two of which have a vertex in common. The number of these inG is writtenp(G, k). Using an idea due to L. H. Harper, we establish a condition under which these numbers are approximately normally distributed. We show that our condition is satisfied ifn=|V(G)| is large compared to the maximum degree Δ of a vertex inG(i.e. Δ=o(n)) orG is a large complete graph. One corollary of these results is that the number of points fixed by a randomly chosen involution in the symmetric groupS is asymptotically normally distributed.     

Two Tree-Width-Like Graph Invariants

In this paper we introduce two tree-width-like graph invariants. The first graph invariant, which we denote by ⁼(G), is defined in terms of positive semi-definite matrices and is similar to the graph invariant (G), introduced by Colin de Verdière in [J. Comb. Theory, Ser. B., 74:121–146, 1998]. The second graph invariant, which we denote by (G), is defined in terms of a certain connected subgraph property and is similar to (G), introduced by van der Holst, Laurent, and Schrijver in [J. Comb. Theory, Ser. B., 65:291–304, 1995]. We give some theorems on the behaviour of these invariants under certain transformations. We show that ⁼(G)=(G) for any graph G with ⁼(G)4, and we give minimal forbidden minor characterizations for the graphs satisfying ⁼(G)k for k=1,2,3,4.This paper is extracted from two chapters of [7]. This work was done while the author was at the Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands.