Chromatic sums of general maps on the sphere and the projective plane

In this paper, we study the chromatic sum functions of rooted general maps on the sphere and the projective plane. The chromatic sum function equations of such maps are obtained. From the chromatic sum equations of such maps, the enumerating function equations of rooted loopless maps, bipartite maps and Eulerian maps are also derived. Moreover, some explicit expressions of enumerating functions are also derived.     

Classification of reflexible regular embeddings and self-Petrie dual regular embeddings of complete bipartite graphs

In this paper, we classify the reflexible regular orientable embeddings and the self-Petrie dual regular orientable embeddings of complete bipartite graphs. The classification shows that for any natural number n, say (p₁,p₂,…,p_k are distinct odd primes and a_i>0 for each i?1), there are t distinct reflexible regular embeddings of the complete bipartite graph K_n,n up to isomorphism, where t=1 if a=0, t=2^k if a=1, t=2^k+1 if a=2, and t=3·2^k+1 if a?3. And, there are s distinct self-Petrie dual regular embeddings of K_n,n up to isomorphism, where s=1 if a=0, s=2^k if a=1, s=2^k+1 if a=2, and s=2^k+2 if a?3.     

Venn diagrams and planar graphs

Using graph theory, we develop procedures for the construction of Venn diagrams. This allows us to determine the number of Venn diagrams on three sets, and to address further questions on enumeration of Venn diagrams. In so doing, we obtain examples of Venn diagrams which yield answers to several problems and conjectures of Grünbaum.Supported in part by a Purdue Research Foundation Summer Faculty Grant.     

Small cycle double covers of 4-connected planar graphs

Acycle double cover of a graph,G, is a collection of cycles,C, such that every edge ofG lies in precisely two cycles ofC. TheSmall Cycle Double Cover Conjecture, proposed by J. A. Bondy, asserts that every simple bridgeless graph onn vertices has a cycle double cover with at mostn–1 cycles, and is a strengthening of the well-knownCycle Double Cover Conjecture. In this paper, we prove Bondy's conjecture for 4-connected planar graphs.     

Minimum edge ranking spanning trees of split graphs

Given a graph G, the minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of G whose edge ranking is minimum. However, this problem is known to be NP-hard for general graphs. In this paper, we show that the problem MERST has a polynomial time algorithm for split graphs, which have useful applications in practice. The result is also significant in the sense that this is a first non-trivial graph class for which the problem MERST is found to be polynomially solvable. We also show that the problem MERST for threshold graphs can be solved in linear time, where threshold graphs are known to be split.     

A polynomial of graphs on surfaces

ribbon graphs , i.e., graphs realized as disks (vertices) joined together by strips (edges) glued to their boundaries, corresponding to neighbourhoods of graphs embedded into surfaces. We construct a four-variable polynomial invariant of these objects, the ribbon graph polynomial, which has all the main properties of the Tutte polynomial. Although the ribbon graph polynomial extends the Tutte polynomial, its definition is very different, and it depends on the topological structure in an essential way. Received: 14 September 2000 / Published online: 18 January 2002     

An algorithm for finding hamilton paths and cycles in random graphs

This paper describes a polynomial time algorithm HAM that searches for Hamilton cycles in undirected graphs. On a random graph its asymptotic probability of success is that of the existence of such a cycle. If all graphs withn vertices are considered equally likely, then using dynamic programming on failure leads to an algorithm with polynomial expected time. The algorithm HAM is also used to solve the symmetric bottleneck travelling salesman problem with probability tending to 1, asn tends to ∞. Various modifications of HAM are shown to solve several Hamilton path problems. Supported by NSF Grant MCS 810 4854.     

Characterization of special hamiltonian graphs

We get a formula for the number of hamiltonian circuits of a graph through which we characterize the special hamiltonian graphs, that is containing a dominant circuit of minimal length.     

Minimum cycle bases of Halin graphs

Halin graphs are planar 3‐connected graphs that consist of a tree and a cycle connecting the end vertices of the tree. It is shown that all Halin graphs that are not “necklaces” have a unique minimum cycle basis. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 150–155, 2003     

Spanning trees of extended graphs

A generalization of the Prüfer coding of trees is given providing a natural correspondence between the set of codes of spanning trees of a graph and the set of codes of spanning trees of theextension of the graph. This correspondence prompts us to introduce and to investigate a notion ofthe spanning tree volume of a graph and provides a simple relation between the volumes of a graph and its extension (and in particular a simple relation between the spanning tree numbers of a graph and its uniform extension). These results can be used to obtain simple purely combinatorial proofs of many previous results obtained by the Matrix-tree theorem on the number of spanning trees of a graph. The results also make it possible to construct graphs with the maximal number of spanning trees in some classes of graphs.     

Connected permutation graphs

A permutation graph is a simple graph associated with a permutation. Let c_n be the number of connected permutation graphs on n vertices. Then the sequence {c_n} satisfies an interesting recurrence relation such that it provides partitions of n! as . We also see that, if uniformly chosen at random, asymptotically almost all permutation graphs are connected.     

Random interval graphs

In this paper we introduce a notion ofrandom interval graphs: the intersection graphs of real, compact intervals whose end points are chosen at random. We establish results about the number of edges, degrees, Hamiltonicity, chromatic number and independence number of almost all interval graphs.     

Path extendable graphs

A pathP in a graphG is said to beextendable if there exists a pathP’ inG with the same endvertices asP such thatV(P)⊆V (P’) and |V(P’)|=|V(P)|+1. A graphG ispath extendable if every nonhamiltonian path inG is extendable. We investigate the extent to which known sufficient conditions for a graph to be hamiltonian-connected imply the extendability of paths in the graph. Several theorems are proved: for example, it is shown that ifG is a graph of orderp in which the degree sum of each pair of non-adjacent vertices is at leastp+1 andP is a nonextendable path of orderk inG thenk≤(p+1)/2 and 〈V (P)〉≅K _k orK _k −e. As corollaries of this we deduce that if δ(G)≥(p+2)/2 or if the degree sum of each pair of nonadjacent vertices inG is at least (3p−3)/2 thenG is path extendable, which strengthen results of Williamson [13].     

Contractions of graphs with no spanning eulerian subgraphs

Letp2 be a fixed integer, and letG be a connected graph onn vertices. If(G)2, ifd(u)+d(v)>2n/p–2 holds wheneveruvE(G), and ifn is sufficiently large compared top, then eitherG has a spanning eulerian subgraph, orG is contractible to a graphG ₁ of order less thenp and with no spanning eulerian subgraph. The casep=2 was proved by Lesniak-Foster and Williamson. The casep=5 was conjectured by Benhocine, Clark, Köhler, and Veldman, when they proved virtually the casep=3. The inequality is best-possible.     

Dirac type condition and Hamiltonian-connected graphs

Abstract

In 1952 Dirac introduced the Dirac type condition and proved that if G is a connected graph of order n ≥ 3 such that δ(G) ≥ n/2, then G is Hamiltonian. In this paper we consider Hamiltonian-connectedness, which extends the Hamiltonian graphs and prove that if G is a connected graph of order n ≥ 3 such that δ(G) ≥ (n ?1)/2, then G is Hamiltonian-connected or G belongs to five families of well-structured graphs. Thus, the condition and the result generalize the above condition and results of Dirac, respectively.     

Proof of the Seymour conjecture for large graphs

Paul Seymour conjectured that any graphG of ordern and minimum degree of at leastk/k+1n contains thekth power of a Hamiltonian cycle. Here, we prove this conjecture for sufficiently largen.     

Spectrum of the Kerzman–Stein Operator for Model Domains

For a domain , the Kerzman-Stein operator is the skew-hermitian part of the Cauchy operator acting on L²(b), which is defined with respect to Euclidean measure. In this paper we compute the spectrum of the Kerzman-Stein operator for three domains whose boundaries consist of two circular arcs: a strip, a wedge, and an annulus. We also treat the case of a domain bounded by two logarithmic spirals.     

H-extension of graphs

We consider the problem of constructing a graphG* from a collection of isomorphic copies of a graphG in such a way that for every two copies ofG, either no vertices or a section graph isomorphic to a graphH is identified. It is shown that ifG can be partitioned into vertex-disjoint copies ofH, thenG* can be made to have at most |H| orbits. A condition onG so thatG* can be vertextransitive is also included.     

Subpancyclicity of line graphs and degree sums along paths

A graph is called subpancyclic if it contains a cycle of length ? for each ? between 3 and the circumference of the graph. We show that if G is a connected graph on n?146 vertices such that d(u)+d(v)+d(x)+d(y)>(n+10/2) for all four vertices u,v,x,y of any path P=uvxy in G, then the line graph L(G) is subpancyclic, unless G is isomorphic to an exceptional graph. Moreover, we show that this result is best possible, even under the assumption that L(G) is hamiltonian. This improves earlier sufficient conditions by a multiplicative factor rather than an additive constant.     

Smallest maximally nonhamiltonian graphs

A graphG ismaximally nonhamiltonian iffG is not hamiltonian butG + e is hamiltonian for each edgee inG ^c, i.e., any two non-adjacent vertices ofG are ends of a hamiltonian path. Bollobás posed the problem of finding the least number of edges,f(n), possible in a maximally nonhamiltonian graph of ordern. Results of Bondy show thatf(n) 3/2 n forn 7. We exhibit graphs of even ordern 36 for which the bound is attained. These graphs are the snarks,J _k, of Isaacs and mild variations of them. For oddn 55 we construct graphs from the graphsJ _k showing that in this case,f(n) = 3n + 1/2 or 3n + 3/2 and leave the determination of which is correct as an open problem. Finally we note that the graphsJ _k, k 7 are hypohamiltonian cubics with girth 6.