Enumeration of labeled bicyclic and tricyclic Eulerian graphs

Explicit formulas for the number of labeled bicyclic and tricyclic Eulerian graphs and for the number of labeled tricyclic Eulerian blocks are obtained. Many-vertex asymptotics for these numbers are found.     

Enumeration of labeled block-cactus graphs

The exact and asymptotic formulas are obtained for the number of block-cactus graphs and Eulerian block-cactus graphs with a given number of vertices.     

Enumeration of labeled,three-connected graphs

The technique of functional Legendre transformations developed in statistical physics and quantum field theory is used to enumerate labeled graphs and multi-graphs.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 120, pp. 21–24, 1982.     

Q‐integral unicyclic,bicyclic and tricyclic graphs

A graph is called Q‐integral if its signless Laplacian spectrum consists of integers. In this paper, we characterize a class of k‐cyclic graphs whose second smallest signless Laplacian eigenvalue is less than one. Using this result we determine all the Q‐integral unicyclic, bicyclic and tricyclic graphs.     

Enumeration of labeled,connected, homeomorphically irreducible graphs

Translated from Matematicheskie Zametki, Vol. 49, No. 3, pp. 12–22, March, 1991.     

Enumeration of labeled geodetic graphs with small cyclomatic number

Explicit expressions for the numbers of labeled geodetic bicyclic, tricyclic, and tetracyclic graphs with a given number of vertices are obtained.     

Enumeration of labeled connected graphs with given order and size

We deduce a new formula for the number of labeled connected graphs with given order and number of edges in terms of the block generating function. Applying this formula, we exactly and asymptotically enumerate cacti with given order and cyclomatic number.     

Enumeration of rooted nonseparable outerplanar maps

In this paper, the number of combinatorially distinct rooted nonseparable outerplanar maps withm edges and the valency of the root-face being n is found to be(m-1)! (m-2) !:(n-1)!(n-2)! (m-n)!(m-n 1)!and, the number of rooted nonseparable outerplanar maps with m edges is also determined to be(2m-2)!:(m-1)!m!,which is just the number of distinct rooted plane trees with m-1 edges.     

Pathwidth of outerplanar graphs

We are interested in the relation between the pathwidth of a biconnected outerplanar graph and the pathwidth of its (geometric) dual. Bodlaender and Fomin [3], after having proved that the pathwidth of every biconnected outerplanar graph is always at most twice the pathwidth of its (geometric) dual plus two, conjectured that there exists a constant c such that the pathwidth of every biconnected outerplanar graph is at most c plus the pathwidth of its dual. They also conjectured that this was actually true with c being one for every biconnected planar graph. Fomin [10] proved that the second conjecture is true for all planar triangulations. First, we construct for each p ≥ 1, a biconnected outerplanar graph of pathwidth 2p + 1 whose (geometric) dual has pathwidth p + 1, thereby disproving both conjectures. Next, we also disprove two other conjectures (one of Bodlaender and Fomin [3], implied by one of Fomin [10]. Finally we prove, in an algorithmic way, that the pathwidth of every biconnected outerplanar graph is at most twice the pathwidth of its (geometric) dual minus one. A tight interval for the studied relation is therefore obtained, and we show that all cases in the interval happen. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 27–41, 2007     

A generalization of outerplanar graphs

Let G be a planar graph and W a set of vertices, G is W-outerplanar if it can be embedded in the plane so that all vertices of W lie on the exterior face. We give a characterization of these graphs by forbidden subgraphs, an upper bound on the number of edges, and other properties which lead to an algorithm of W-outerplanarity testing.     

The reconstruction of outerplanar graphs

Ulam's conjecture is that a graph G with at least three vertices can be reconstructed from the family of subgraphs of G obtained by deleting single vertices of G. This paper proves the conjecture for G outerplanar, by working first with partially labeled graphs and then applying the results obtained to the unlabeled case.     

Centers of maximal outerplanar graphs

The center of a graph is defined to be the subgraph induced by the set of vertices that have minimum eccentricities (i.e., minimum distance to the most distant vertices). It is shown that only seven graphs can be centers of maximal outerplanar graphs.     

Minimum rank of outerplanar graphs

The problem of finding the minimum rank over all symmetric matrices corresponding to a given graph has grown in interest recently. It is well known that the minimum rank of any graph is bounded above by the clique cover number, the minimum number of cliques needed to cover all edges of the graph. We generalize the idea of the clique cover number by defining the rank sum of a cover to be the sum of the minimum ranks of the graphs in the cover. Using this idea we obtain a combinatorial solution to the minimum rank problem for an outerplanar graph. As a consequence the minimum rank of an outerplanar graph is field independent and all outerplanar graphs have a universally optimal matrix. We also consider implications of the main result to the inverse inertia problem.     

On reconstructing maximal outerplanar graphs

Manvel has proved that a maximal outerplanar graph can be reconstructed from the collection of isomorphism types of subgraphs obtained by deleting vertices of the given graph. This paper sharpens Manvel's result by showing that if the graph is not a triangulation of a hexagon, then reconstruction can be accomplished using only those isomorphism types of subgraphs corresponding to deletion of vertices of valence two.     

Approximation of pathwidth of outerplanar graphs

There exists a polynomial time algorithm to compute the pathwidth of outerplanar graphs, but the large exponent makes this algorithm impractical. In this paper, we give an algorithm that, given a biconnected outerplanar graph G, finds a path decomposition of G of pathwidth at most twice the pathwidth of G plus one. To obtain the result, several relations between the pathwidth of a biconnected outerplanar graph and its dual are established.     

Algebraic characterizations of outerplanar and planar graphs

A drawing of a graph in the plane is even if nonadjacent edges have an even number of intersections. Hanani’s theorem characterizes planar graphs as those graphs that have an even drawing. In this paper we present an algebraic characterization of graphs that have an even drawing. Together with Hanani’s theorem this yields an algebraic characterization of planar graphs. We will also present algebraic characterizations of subgraphs of paths, and of outerplanar graphs.     

Game chromatic number of outerplanar graphs

This note proves that the game chromatic number of an outerplanar graph is at most 7. This improves the previous known upper bound of the game chromatic number of outerplanar graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 67–70, 1999     

Colouring games on outerplanar graphs and trees

Let f be a graph function which assigns to each graph H a non-negative integer f(H)≤|V(H)|. The f-game chromatic number of a graph G is defined through a two-person game. Let X be a set of colours. Two players, Alice and Bob, take turns colouring the vertices of G with colours from X. A partial colouring c of G is legal (with respect to graph function f) if for any subgraph H of G, the sum of the number of colours used in H and the number of uncoloured vertices of H is at least f(H). Both Alice and Bob must colour legally (i.e., the partial colouring produced needs to be legal). The game ends if either all the vertices are coloured or there are uncoloured vertices with no legal colour. In the former case, Alice wins the game. In the latter case, Bob wins the game. The f-game chromatic number of G, χ_g(f,G), is the least number of colours that the colour set X needs to contain so that Alice has a winning strategy. Let be the graph function defined as , for any n≥3 and otherwise. Then is called the acyclic game chromatic number of G. In this paper, we prove that any outerplanar graph G has acyclic game chromatic number at most 7. For any integer k, let ?_k be the graph function defined as ?_k(K₂)=2 and ?_k(P_k)=3 (P_k is the path on k vertices) and ?_k(H)=0 otherwise. This paper proves that if k≥8 then for any tree T, χ_g(?_k,T)≤9. On the other hand, if k≤6, then for any integer n, there is a tree T such that χ_g(?_k,T)≥n.