A quadratic identity for the number of perfect matchings of plane graphs

We present a quadratic identity on the number of perfect matchings of plane graphs by the method of graphical condensation, which generalizes the results found by Propp [J. Propp, Generalized domino-shuffling, Theoret. Comput. Sci. 303 (2003) 267–301], Kuo [E.H. Kuo, Applications of graphical condensation for enumerating matchings and tilings, Theoret. Comput. Sci. 319 (2004) 29–57], and Yan, Yeh, and Zhang [W.G. Yan, Y.-N. Yeh, F.J. Zhang, Graphical condensation of plane graphs: A combinatorial approach, Theoret. Comput. Sci. 349 (2005) 452–461].     

A structure theorem for maximum internal matchings in graphs

A counterpart of the Gallai-Edmonds Structure Theorem is proved for matchings that are not required to cover the external vertices of graphs. The appropriate counterpart of Tutte's Theorem is derived from this result for the existence of perfect internal matchings in graphs.     

A spectral lower bound for the treewidth of a graph and its consequences

We give a lower bound for the treewidth of a graph in terms of the second smallest eigenvalue of its Laplacian matrix. We use this lower bound to show that the treewidth of a d-dimensional hypercube is at least ⌊3·2^d/(2(d+4))⌋−1. The currently known upper bound is . We generalize this result to Hamming graphs. We also observe that every graph G on n vertices, with maximum degree Δ

(1)

contains an induced cycle (chordless cycle) of length at least 1+log_Δ(μn/8) (provided G is not acyclic),

(2)

has a clique minor K_h for some ,

where μ is the second smallest eigenvalue of the Laplacian matrix of G.     

A lower bound for the hitting set size for combinatorial rectangles and an application

We prove a lower bound of where for the hitting set size for combinatorial rectangles of volume at least ε in [m]^d space, for and d>2.     

A notion of cross-perfect bipartite graphs

In this note, we consider four quantities defined on a bipartite graph B: the cross-chromatic index χ∗(B), the biclique number w∗(B), the cross-free matching number m∗(B) and the biclique edge covering number β∗(B). We mention several applications of these numbers and define a notion of cross-perfect bipartite graphs. A duality between these numbers for the class of cross-perfect graphs is examined.     

A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs

We study a problem of lower bounds on straight line drawings of planar graphs. We show that at least 1.235·n points in the plane are required to draw each n-vertex planar graph with edges drawn as straight line segments (for sufficiently large n). This improves the previous best bound of 1.206·n (for sufficiently large n) due to Chrobak and Karloff [Sigact News 20 (4) (1989) 83-86]. Our contribution is twofold: we improve the lower bound itself and we give a significantly simpler and more straightforward proof.     

Distortion lower bounds for line embeddings

In this paper, we show how we can derive lower bounds and also compute the exact distortion for the line embeddings of some special metrics, especially trees and graphs with certain structure. Using linear programming to formulate a simpler version of the problem gives an interesting intuition and direction concerning the computation of general lower bounds for distortion into the line. We also show that our lower bounds on special cases of metrics are a lot better than previous lower bounds.     

A sufficient condition for a planar graph to be 3-choosable

It is shown that a planar graph without cycles of length 4, 6, 8, or 9 is 3-choosable.     

Partition-distance: A problem and class of perfect graphs arising in clustering

Partitioning of a set of elements into disjoint clusters is a fundamental problem that arises in many applications. Different methods produce different partitions, so it is useful to have a measure of the similarity, or distance, between two or more partitions. In this paper we examine one distance measure used in a clustering application in computational genetics. We show how to efficiently compute the distance, and how this defines a new class of perfect graphs.     

Random parallel algorithms for finding exact branchings,perfect matchings,and cycles

In this paper we devise randomized parallel algorithms which given a unary weighted (di)graphG=(V, E)construct in time O(log²¦ V¦) branchings, perfect matchings, and disjoint cycles of weightexactly k belonging toG. These problems have been studied by Papadimitriou and Yannakakis [PY1], by Barahona and Pulleyblank [BP], by Cameriniet al [CGM], and by Mulmuleyet al. [MVV]. Our algorithms improve previous solutions. Moreover, we give an NC² algorithm for computing the absolute value of the pfaffian of a skew-symmetric matrix.Supported in part by MURST 40%.     

An exact upper bound to the maximum number of perfect matchings in cubic pseudographs

The present paper shows that the function Φ (n)=2ⁿ+1 is an upper bound to the maximum number of distinct perfect matchings in cubic, connected pseudographs with2n vertices. Moreover examples of pseudographs are given which exactly realize such a bound. This work was carried out while the author was visiting the Department of Electrical Engineering and Computer Science of the University of California at Berkeley. It was supported in part by a grant from Consiglio Nazionale delle Ricerche, Roma, Italy.     

The 2-dipath chromatic number of Halin graphs

A 2-dipath k-coloring f of an oriented graph is a mapping from to the color set {1,2,…,k} such that f(x)≠f(y) whenever two vertices x and y are linked by a directed path of length 1 or 2. The 2-dipath chromatic number of is the smallest k such that has a 2-dipath k-coloring. In this paper we prove that if is an oriented Halin graph, then . There exist infinitely many oriented Halin graphs such that .     

On graphs with the third largest number of maximal independent sets

Let G be a simple and undirected graph. By mi(G) we denote the number of maximal independent sets in G. Erd?s and Moser posed the problem to determine the maximum cardinality of mi(G) among all graphs of order n and to characterize the corresponding extremal graphs attaining this maximum cardinality. The above problem has been solved by Moon and Moser in [J.W. Moon, L. Moser, On cliques in graphs, Israel J. Math. 3 (1965) 23-28]. More recently, Jin and Li [Z. Jin, X. Li, Graphs with the second largest number of maximal independent sets, Discrete Mathematics 308 (2008) 5864-5870] investigated the second largest cardinality of mi(G) among all graphs of order n and characterized the extremal graph attaining this value of mi(G). In this paper, we shall determine the third largest cardinality of mi(G) among all graphs G of order n. Additionally, graphs achieving this value are also determined.     

On the oriented chromatic number of Halin graphs

An oriented k-coloring of an oriented graph G is a mapping such that (i) if xy∈E(G) then c(x)≠c(y) and (ii) if xy,zt∈E(G) then c(x)=c(t)⇒c(y)≠c(z). The oriented chromatic number of an oriented graph G is defined as the smallest k such that G admits an oriented k-coloring. We prove in this paper that every Halin graph has oriented chromatic number at most 9, improving a previous bound proposed by Vignal.     

The number of spanning trees of a graph with given matching number

The number of spanning trees of a graph G is the total number of distinct spanning subgraphs of G that are trees. In this paper, we present sharp upper bounds for the number of spanning trees of a graph with given matching number.