Counting unrooted maps on the plane

A planar map is a 2-cell embedding of a connected planar graph, loops and parallel edges allowed, on the sphere. A plane map is a planar map with a distinguished outside (“infinite”) face. An unrooted map is an equivalence class of maps under orientation-preserving homeomorphism, and a rooted map is a map with a distinguished oriented edge. Previously we obtained formulae for the number of unrooted planar n-edge maps of various classes, including all maps, non-separable maps, eulerian maps and loopless maps. In this article, using the same technique we obtain closed formulae for counting unrooted plane maps of all these classes and their duals. The corresponding formulae for rooted maps are known to be all sum-free; the formulae that we obtain for unrooted maps contain only a sum over the divisors of n. We count also unrooted two-vertex plane maps.     

On the Signed Domination in Graphs

G on n vertices with minimum degree r, there exists a two-coloring of the vertices of G with colors +1 and -1, such that the closed neighborhood of each vertex contains more +1's than -1's, and altogether the number of 1's does not exceed the number of -1's by more than . As a construction by Füredi and Mubayi shows, this is asymptotically tight. The proof uses the partial coloring method from combinatorial discrepancy theory. Received May 12, 1998     

A characterisation of rigid circuit graphs

Let G_n be a graph of n vertices, having chromatic number r which contains no complete graph of r vertices. Then G_n contains a vertex of degree not exceeding n(3r?7)/(3r?4). The result is essentially best possible.     

Parity vertex colouring of plane graphs

A proper vertex colouring of a 2-connected plane graph G is a parity vertex colouring if for each face f and each colour c, either no vertex or an odd number of vertices incident with f is coloured with c. The minimum number of colours used in such a colouring of G is denoted by χ_p(G).In this paper, we prove that χ_p(G)≤118 for every 2-connected plane graph G.     

Local and global average degree in graphs and multigraphs

A vertex v of a graph G is called groupie if the average degree t_v of all neighbors of v in G is not smaller than the average degree t_G of G. Every graph contains a groupie vertex; the problem of whether or not every simple graph on ≧2 vertices has at least two groupie vertices turned out to be surprisingly difficult. We present various sufficient conditions for a simple graph to contain at least two groupie vertices. Further, we investigate the function f(n) = max min_v (t_v/t_G), where the maximum ranges over all simple graphs on n vertices, and prove that f(n) = 1/42n + o(1). The corresponding result for multigraphs is in sharp contrast with the above. We also characterize trees in which the local average degree t_v is constant.     

An Ore-type condition for arbitrarily vertex decomposable graphs

Let G be a graph of order n and r, 1≤r≤n, a fixed integer. G is said to be r-vertex decomposable if for each sequence (n₁,…,n_r) of positive integers such that n₁+?+n_r=n there exists a partition (V₁,…,V_r) of the vertex set of G such that for each i∈{1,…,r}, V_i induces a connected subgraph of G on n_i vertices. G is called arbitrarily vertex decomposable if it is r-vertex decomposable for each r∈{1,…,n}.In this paper we show that if G is a connected graph on n vertices with the independence number at most ⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n−3, then G is arbitrarily vertex decomposable or isomorphic to one of two exceptional graphs. We also exhibit the integers r for which the graphs verifying the above degree-sum condition are not r-vertex decomposable.     

An analogue of the Harer-Zagier formula for unicellular maps on general surfaces

A unicellular map is the embedding of a connected graph in a surface in such a way that the complement of the graph is simply connected. In a famous article, Harer and Zagier established a formula for the generating function of unicellular maps counted according to the number of vertices and edges. The keystone of their approach is a counting formula for unicellular maps on orientable surfaces with n edges, and with vertices colored using every color in [q] (adjacent vertices are authorized to have the same color). We give an analogue of this formula for general (locally orientable) surfaces.Our approach is bijective and is inspired by Lass?s proof of the Harer-Zagier formula. We first revisit Lass?s proof and twist it into a bijection between unicellular maps on orientable surfaces with vertices colored using every color in [q], and maps with vertex set [q] on orientable surfaces with a marked spanning tree. The bijection immediately implies Harer-Zagier?s formula and a formula by Jackson concerning bipartite unicellular maps. It also shed a new light on constructions by Goulden and Nica, Schaeffer and Vassilieva, and Morales and Vassilieva. We then extend the bijection to general surfaces and obtain a correspondence between unicellular maps on general surfaces with vertices colored using every color in [q], and maps on orientable surfaces with vertex set [q]with a marked planar submap. This correspondence gives an analogue of the Harer-Zagier formula for general surfaces. We also show that this formula implies a recursion formula due to Ledoux for the numbers of unicellular maps with given numbers of vertices and edges.     

The Semi-Arc Automorphism Group of a Graph with Application to Map Enumeration

A map is a connected topological graph cellularly embedded in a surface. For a given graph Γ, its genus distribution of rooted maps and embeddings on orientable and non-orientable surfaces are separately investigated by many researchers. By introducing the concept of a semi-arc automorphism group of a graph and classifying all its embeddings under the action of its semi-arc automorphism group, we find the relations between its genus distribution of rooted maps and genus distribution of embeddings on orientable and non-orientable surfaces, and give some new formulas for the number of rooted maps on a given orientable surface with underlying graph a bouquet of cycles B_n, a closed-end ladder L_n or a Ringel ladder R_n. A general scheme for enumerating unrooted maps on surfaces(orientable or non-orientable) with a given underlying graph is established. Using this scheme, we obtained the closed formulas for the numbers of non-isomorphic maps on orientable or non-orientable surfaces with an underlying bouquet B_n in this paper.     

Perfect fractional matchings in random hypergraphs

Given an r-uniform hypergraph H = (V, E) on |V| = n vertices, a real-valued function f:E→R⁺ is called a perfect fractional matching if Σ_vϵe f(e) ≤ 1 for all vϵV and Σ_eϵE f(e) = n/r. Considering a random r-uniform hypergraph process of n vertices, we show that with probability tending to 1 as n→ infinity, at the very moment t₀ when the last isolated vertex disappears, the hypergraph H_t0 has a perfect fractional matching. This result is clearly best possible. As a consequence, we derive that if p(n) = (ln n + w(n))/ , where w(n) is any function tending to infinity with n, then with probability tending to 1 a random r-uniform hypergraph on n vertices with edge probability p has a perfect fractional matching. Similar results hold also for random r-partite hypergraphs. © 1996 John Wiley & Sons, Inc.     

A Note on a Generalization of the Multiple Cover Formula and the Simple Flop

We prove a closed formula for an excess integral over the moduli space of stable maps from genus one, unmarked curves to the projective space ? ^r of degree d for any positive integers r and d. The result generalizes the multiple cover formula for ?¹. We also show that any simple ? ^r flop preserves the theory of arbitrary-genus Gromov-Witten invariants in exceptional curve classes.     

Equivelar maps on the torus

We give a classification of all equivelar polyhedral maps on the torus. In particular, we classify all triangulations and quadrangulations of the torus admitting a vertex transitive automorphism group. These are precisely the ones which are quotients of the regular tessellations {3,6}, {6,3} or {4,4} by a pure translation group. An explicit formula for the number of combinatorial types of equivelar maps (polyhedral and non-polyhedral) with n vertices is obtained in terms of arithmetic functions in elementary number theory, such as the number of integer divisors of n. The asymptotic behaviour for n→∞ is also discussed, and an example is given for n such that the number of distinct equivelar triangulations of the torus with n vertices is larger than n itself. The numbers of regular and chiral maps are determined separately, as well as the ones for all other kinds of symmetry. Furthermore, arithmetic properties of the integers of type p²+pq+q² (or p²+q², resp.) can be interpreted and visualized by the hierarchy of covering maps between regular and chiral equivelar maps or type {3,6} (or {4,4}, resp.).     

A lower bound for groupies in graphs

A non-isolated vertex of a graph G is called a groupie if the average degree of the vertices connected to it is larger than or equal to the average degree of the vertices in G. An isolated vertex is a groupie only if all vertices of G are isolated. While it is well known that every graph must contain at least one groupie, the graph K_n − e contains just 2 groupie vertices for n ≥ 2. In this paper we derive a lower bound for the number of groupies which shows, in particular, that any graph with 2 or more vertices must contain at least 2 groupies. © 1996 John Wiley & Sons, Inc.     

Domination number in graphs with minimum degree two

A set D of vertices of a graph G = （V, E） is called a dominating set if every vertex of V not in D is adjacent to a vertex of D. In 1996, Reed proved that every graph of order n with minimum degree at least 3 has a dominating set of cardinality at most 3n/8. In this paper we generalize Reed＇s result. We show that every graph G of order n with minimum degree at least 2 has a dominating set of cardinality at most （3n ＋IV21）/8, where V2 denotes the set of vertices of degree 2 in G. As an application of the above result, we show that for k ≥ 1, the k-restricted domination number rk （G, γ） ≤ （3n＋5k）/8 for all graphs of order n with minimum degree at least 3.     

Counting rooted unicursal planar maps

This paper investigates the number of rooted unicursal planar maps and presents some formulae for such maps with four parameters： the numbers of nonrooted vertices and inner faces and the valencies of two odd vertices.     

On double and multiple interval graphs

In this paper we discuss a generalization of the familiar concept of an interval graph that arises naturally in scheduling and allocation problems. We define the interval number of a graph G to be the smallest positive integer t for which there exists a function f which assigns to each vertex u of G a subset f(u) of the real line so that f(u) is the union of t closed intervals of the real line, and distinct vertices u and v in G are adjacent if and only if f(u) and f(v)meet. We show that (1) the interval number of a tree is at most two, and (2) the complete bipartite graph K_{m, n} has interval number ?(mn + 1)/(m + n)?.     

The rationality of the Hilbert-Kunz multiplicity in graded dimension two

We show that the Hilbert-Kunz multiplicity is a rational number for an R₊−primary homogeneous ideal I=(f₁, . . . , f_n) in a two-dimensional graded domain R of finite type over an algebraically closed field of positive characteristic. More specific, we give a formula for the Hilbert-Kunz multiplicity in terms of certain rational numbers coming from the strong Harder-Narasimhan filtration of the syzygy bundle Syz(f₁, . . . , f_n) on the projective curve Y=ProjR.     

Edge-Colorings with No Large Polychromatic Stars

 Given a graph G and a positive integer r, let f _r (G) denote the largest number of colors that can be used in a coloring of E(G) such that each vertex is incident to at most r colors. For all positive integers n and r, we determine f _r (K _n,n ) exactly and f _r (K _n ) within 1. In doing so, we disprove a conjecture by Manoussakis, Spyratos, Tuza and Voigt in [4]. Received: May 17, 1999 Final version received: January 12, 2000     

Symmetry classes of spanning trees of Aztec diamonds and perfect matchings of odd squares with a unit hole

We say that two graphs are similar if their adjacency matrices are similar matrices. We show that the square grid G _n of order n is similar to the disjoint union of two copies of the quartered Aztec diamond QAD _n−1 of order n−1 with the path P _n ⁽²⁾ on n vertices having edge weights equal to 2. Our proof is based on an explicit change of basis in the vector space on which the adjacency matrix acts. The arguments verifying that this change of basis works are combinatorial. It follows in particular that the characteristic polynomials of the above graphs satisfy the equality P(G _n )=P(P _n ⁽²⁾)[P(QAD _n−1)]². On the one hand, this provides a combinatorial explanation for the “squarishness” of the characteristic polynomial of the square grid—i.e., that it is a perfect square, up to a factor of relatively small degree. On the other hand, as formulas for the characteristic polynomials of the path and the square grid are well known, our equality determines the characteristic polynomial of the quartered Aztec diamond. In turn, the latter allows computing the number of spanning trees of quartered Aztec diamonds. We present and analyze three more families of graphs that share the above described “linear squarishness” property of square grids: odd Aztec diamonds, mixed Aztec diamonds, and Aztec pillowcases—graphs obtained from two copies of an Aztec diamond by identifying the corresponding vertices on their convex hulls. We apply the above results to enumerate all the symmetry classes of spanning trees of the even Aztec diamonds, and all the symmetry classes not involving rotations of the spanning trees of odd and mixed Aztec diamonds. We also enumerate all but the base case of the symmetry classes of perfect matchings of odd square grids with the central vertex removed. In addition, we obtain a product formula for the number of spanning trees of Aztec pillowcases. Research supported in part by NSF grant DMS-0500616.     

A Degree Constraint for Uniquely Hamiltonian Graphs

A graph, G, is called uniquely Hamiltonian if it contains exactly one Hamilton cycle. We show that if G=(V, E) is uniquely Hamiltonian then Where #(G)=1 if G has even number of vertices and 2 if G has odd number of vertices. It follows that every n-vertex uniquely Hamiltonian graph contains a vertex whose degree is at most c log₂n+2 where c=(log₂3−1)⁻¹≈1.71 thereby improving a bound given by Bondy and Jackson [3].     

Signed graph factors and degree sequences

For a signed graph G and function , a signed f‐factor of G is a spanning subgraph F such that sdeg_F(υ) = f(υ) for every vertex υ of G, where sdeg(υ) is the number of positive edges incident with v less the number of negative edges incident with υ, with loops counting twice in either case. For a given vertex‐function f, we provide necessary and sufficient conditions for a signed graph G to have a signed f‐factor. As a consequence of this result, an Erd?s‐Gallai‐type result is given for a sequence of integers to be the degree sequence of a signed r‐graph, the graph with at most r positive and r negative edges between a given pair of distinct vertices. We discuss how the theory can be altered when mixed edges (i.e., edges with one positive and one negative end) are allowed, and how it applies to bidirected graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 27–36, 2006