Solution of the Hamiltonian problem for self-complementary graphs

A graph G is said to be highly constricted if there exists a nonempty subset S of vertices such that (i) G ? S has more than |S| components, (ii) S induces the complete graph, and (iii) for every u ∈ S and v ? S, we have d_G(u) > d_G(v), where d_G(u) denotes the degree of u in G. In this paper it is shown that a non-hamiltonian self-complementary graph G of order p is highly constricted, unless p = 4N and G is a particular graph $\text{G}{}^1\text{(4N)}$. It is also proved that if G is a self-complementary graph of order p(≥8) and π its degree sequence, then G is pancyclic if π has a realization with a hamiltonian cycle, and G has a 2-factor if π has a realization with a 2-factor, unless p = 4N and $\text{G = G}{}^1\text{(4N)}$.     

Infinite Eulerian tessellations

An Eulerian path in a graph G is a path π such that (1) π traverses each edge of G exactly once in each direction, and (2) π does not traverse any edge once in one direction and then immediately after in the other direction. A tessellation T of the plane is Eulerian if its l-skeleton G admits an Eulerian path. It is shown that the three regular tessellations of the Euclidean plane are Eulerian. More generally, if T is a tessellation of the plane such that each face has 2t least p sides and each vertex has degree (number of incident edges) at least q, where $\text{1/p+1/q≤}\text{1}\text{2}$, then, except possibly for the case p = 3 and q = 6, T is Eulerian. Let $\text{T}{}^1$ be the truncation of T. If every vertex of T has degree 3, then $\text{T}{}^1$ is not Eulerian. If every vertex has degree 4, or degree at least 6, then T is Eulerian.     

Random near-regular graphs and the node packing problem

Nemhauser and Trotter [12] proposed a certain easily-solved linear program as a relaxation of the node packing problem. They showed that any variables receiving integer values in an optimal solution to this linear program also take on the same values in an optimal solution to the (integer) node packing problem. Let π be the property of graphs defined as follows: a graph G has property π if and only if there is a unique optimal solution to the linear-relaxation problem, and this solution is completely fractional. If a graph G has property π then no information about the node packing problem on G is gained by solving the linear relaxation. We calculate the asymptotic probability that a certain type of ‘sparse’ random graph has property π, as the number of its nodes tends to infinity. Let m be a fixed positive integer, and consider the following random graph on the node set {1,2 …, n}). We join each node, j say, to exactly m other nodes chosen randomly with replacement, by edges oriented away from j; we denote by G_n(m) the undirected graph obtained by deleting all orientations and allowing all parallel edges to coalesce. We show that, as n → ∞,

$\text{P(G}{}_{\mathrm{n}}\text{(m)}\text{has property}\text{π)→}\text{0}\text{if}\text{m = 1,}\text{1}\text{if}\text{m ? 3,}$

and we conjecture that $\text{P(G}{}_{\mathrm{n}}\text{(2)}\text{has property}\text{π)→ (1–2e}{}^{\mathrm{?2}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$.     

Results on the edge-connectivity of graphs

It is shown that if G is a graph of order p ≥ 2 such that deg u + deg v ≥ p ? 1 for all pairs u, v of nonadjacent vertices, then the edge-connectivity of G equals the minimum degree of G. Furthermore, if deg u + deg v ≥ p for all pairs u, v of nonadjacent vertices, then either p is even and G is isomorphic to $\text{K}{}_{\mathrm{<mtext>p</mtext><mtext>2</mtext>}}\text{× K}{}_2$ or every minimum cutset of edges of G consists of the collection of edges incident with a vertex of least degree.     

Duality of infinite graphs

Some basic results on duality of infinite graphs are established and it is proven that a block has a dual graph if and only if it is planar and any two vertices are separated by a finite edge cut. Also, the graphs having predual graphs are characterized completely and it is shown that if $\text{G}{}^1$ is a dual and predual graph of G, then G and $\text{G}{}^1$ can be represented as geometric dual graphs. The uniqueness of dual graphs is investigated, in particular, Whitney's 2-isomorphism theorem is extended to infinite graphs. Finally, infinite minimal cuts in dual graphs are studied and the characterization (in terms of planarity and separation properties) of the graphs having dual graphs satisfying conditions on the infinite cuts, as well, is included.     

The binding number of a graph and its Anderson number

The binding number of a graph G, bind(G), is defined; some examples of its calculation are given, and some upper bounds for it are proved. It is then proved that, if bind(G) ≥ c, then G contains at least $\text{|G|}\text{c}\text{(c + 1)}$ disjoint edges if $\text{0 ≤ c ≤}\text{1}\text{2}$, at least $\text{| G |}\text{(3c ? 2)}\text{3c}\text{?}\text{2(c ? 1)}\text{c}$ disjoint edges if $\text{1 ≤ c ≤}\text{4}\text{3}$, a Hamiltonian circuit if $\text{c ≥}\text{3}\text{2}$, and a circuit of length at least $\text{3(| G | ?1)(c ? 1)}\text{c}$ if $\text{1 < c ≤}\text{3}\text{2}$ and G is not one of two specified exceptional graphs. Each of these results is best possible.The Anderson number of a graph is defined. The Anderson numbers of a few very simple graphs are determined; and some rather weak bounds are obtained, and some conjectures made, on the Anderson numbers of graphs in general.     

Hamiltonian cycles in particular k-partite graphs

Let $\text{G}$(itk, p) denote the class of k-partite graphs, where each part is a stable set of cardinality p and where the edges between any pair of stable sets are those of a perfect matching. Maru?i? has conjectured that if G belongs to $\text{G}$(k, p) and is connected then G is hamiltonian. It is proved that the conjecture is true for k ≤ 3 or p ≤ 3; but for k ≥ 4 and p ≥ 4 a non-hamiltonian connected graph in $\text{G}$(k, p) is constructed.     

Pancyclic graphs and a conjecture of Bondy and Chvátal

A p-vertex graph is called pancyclic if it contains cycles of every length l, 3 ≤ l ≤ p. In this paper we prove the following conjecture of Bondy and Chvátal: If a graph G has vertex degree sequence d₁ ≤ d₂ ≤ … ≤ d_ν, and if $\text{d}{}_{\mathrm{k}}\text{≤ k <}\text{p}\text{2}$ implies d_ν?k ≥ p ? k, then G is pancyclic or bipartite.     

Even subgraphs of bridgeless graphs and 2-factors of line graphs

By Petersen's theorem, a bridgeless cubic multigraph has a 2-factor. Fleischner generalised this result to bridgeless multigraphs of minimum degree at least three by showing that every such multigraph has a spanning even subgraph. Our main result is that every bridgeless simple graph with minimum degree at least three has a spanning even subgraph in which every component has at least four vertices. We deduce that if G is a simple bridgeless graph with n vertices and minimum degree at least three, then its line graph has a 2-factor with at most max{1,(3n-4)/10} components. This upper bound is best possible.     

Computing the boxicity of a graph by covering its complement by cointerval graphs

If $\text{F}$ is a family of sets, its intersection graph has the sets in $\text{F}$ as vertices and an edge between two sets if and only if they overlap. This paper investigates the concept of boxicity of a graph G, the smallest n such that G is the intersection graph of boxes in Euclidean n-space. The boxicity, b(G), was introduced by Roberts in 1969 and has since been studied by Cohen, Gabai, and Trotter. The concept has applications to niche overlap (competition) in ecology and to problems of fleet maintenance in operations research. These applications will be described briefly. While the problem of computing boxicity is in general a difficult problem (it is NP-complete), this paper develops techniques for computing boxicity which give useful bounds. They are based on the simple observation that b(G)≤k if and only if there is an edge covering of $\text{G}$ by spanning subgraphs of $\text{G}$, each of which is a cointerval graph, the complement of an interval graph (a graph of boxicity ≤1.).     

On n-hamiltonian graphs

A graph G of order p ? 3 is called n-hamiltonian, 0 ? n ? p ? 3, if the removal of any m vertices, 0 ? m ? n, results in a hamiltonian graph. A graph G of order p ? 3 is defined to be n-hamiltonian, ?p ? n ? 1, if there exists ?n or fewer pairwise disjoint paths in G which collectively span G. Various conditions in terms of n and the degrees of the vertices of a graph are shown to be sufficient for the graph to be n-hamiltonian for all possible values of n. It is also shown that if G is a graph of order p ? 3 and $\text{K}\text{(G) ? β(G) + n (?p ? n ? p ? 3)}$, then G is n-hamiltonian.     

On complementary graphs with no isolated vertices

Let $\text{G}$ denote the complement of a graph G, and x(G), β₁(G), β₄(G), α₀(G), α₁(G) denote respectively the chromatic number, line-independence number, point-independence number, point-covering number, line-covering number of G, Nordhaus and Gaddum showed that for any graph G of order $\text{p}\text{, {2√p} ? x(G) + x(}\text{G}\text{) ? p + 1}\text{and p}\text{? x(G)·x(}\text{G}\text{) ? [(}\text{1}\text{2}\text{(p + 1))}{}^2\text{]}$. Recently Chartrand and Schuster have given the corresponding inequalities for the independence numbers of any graph G. However, combining their result with Gallai's well known formula β₁(G) + α₁(G) = ?, one is not deduce the analogous bounds for the line-covering numbers of $\text{G}\text{and}\text{G}$, since Gallai's formula holds only if G contains no isolated vertex. The purpose of this note is to improve the results of Chartland and Schuster for line-independence numbers for graphs where both $\text{G}\text{and}\text{G}$ contain no isolated vertices and thereby allowing us to use Gallai's formula to get the corresponding bounds for the line-covering numbers of G.     

On diameter critical graphs

A graph G is diameter k-critical if the graph has diameter k and the deletion of any edge increases its diameter. We show that every diameter 2-critical graph on v vertices has (i) at most 0.27v² edges, and (ii) average edge degree at most $\text{6}\text{5}$v. We also make a conjecture on the maximal number of edges in a diameter k-critical graph.     

The spherical Bochner theorem on semisimple Lie groups

Let G be a connected semisimple Lie group with finite center and K a maximal compact subgroup. Denote (i) Harish-Chandra's Schwartz spaces by $\text{C}$^p(G)(0<p?2), (ii) the K-biinvariant elements in $\text{C}$^p(G) by $\text{I}$^p(G), (iii) the positive definite (zonal) spherical functions by $\text{P}$, and (iv) the spherical transform on $\text{C}$^p(G) by ? → $\text{}\text{?}$gj. For T a positive definite distribution on G it is established that (i) T extends uniquely onto $\text{C}$^l(G), (ii) there exists a unique measure μ of polynomial growth on $\text{P}$ such that T[ψ]=∫pψdμ for all ψ?I¹(G) (iii) all measures μ of polynomial growth on $\text{P}$ are obtained in this way, and (iv) T may be extended to a particular $\text{I}$^p(G) space (1 ? p ? 2) if and only if the support of μ lies in a certain easily defined subset of $\text{P}$. These results generalize a well-known theorem of Godement, and the proofs rely heavily on the recent harmonic analysis results of Trombi and Varadarajan.     

Smoothness and absolute convergence of Fourier series in compact totally disconnected groups

In this paper we study in the context of compact totally disconnected groups the relationship between the smoothness of a function and its membership in the Fourier algebra $\text{G}$G. Specifically, we define a notion of smoothness which is natural for totally disconnected groups. This in turn leads to the notions of Lipshitz condition and bounded variation. We then give a condition on α which if satisfied implies Lip_α(G) ? $\text{R}$(G). On certain groups this condition becomes: $\text{α >}\text{1}\text{2}$ (Bernstein's theorem). We then give a similar condition on α which if satisfied implies that Lip_α(G) ∈ BV(G) ? $\text{R}$(G). On certain groups this condition becomes: α > 0 (Zygmund's theorem). Moreover we show that $\text{α >}\text{1}\text{2}$ is best possible by showing that $\text{Lip}{}_{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{(G)}$ ? $\text{R}$(G).     

Induced representations and finite volume homogeneous spaces

We prove that the representation of $\text{C}{}^1\text{(G ×}\text{G}\text{H}\text{)}$ induced from the restriction to H of a unitary representation π of G can be constructed directly from π in the framework of Rieffel's theory of induced representations of C¹-algebras, with the inducing process defined by a generalized conditional expectation. We then show, in the general context of Rieffel's theory, that if the induced representation is CCR, so is the original. In a more special situation, which still generalizes that of a conditional expectation onto a subalgebra, and which includes the operation of inducing from an open subgroup and the above-mentioned process when $\text{G}\text{H}$ is of finite volume, we prove that if the induced representation is type I, so is the original, and obtain a result on intertwining operators. This provides a unified treatment, as well as an extension to the nonseparable case, of certain known results on induction and restriction of representations.     

Cycles of even length in graphs

In this paper we solve a conjecture of P. Erdös by showing that if a graph Gⁿ has n vertices and at least $\text{100kn}{}^{\mathrm{<mtext>1+</mtext><mtext>1</mtext><mtext>k</mtext>}}$ edges, then G contains a cycle C^2l of length 2l for every integer $\text{l ∈ [k, kn}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}\text{]}$. Apart from the value of the constant this result is best possible. It is obtained from a more general theorem which also yields corresponding results in the case where Gⁿ has only cn(log n)^α edges (α ≥ 1).     

Tough graphs and hamiltonian circuits

The toughness of a graph G is defined as the largest real number t such that deletion of any s points from G results in a graph which is either connected or else has at most s/t components. Clearly, every hamiltonian graph is 1-tough. Conversely, we conjecture that for some t₀, every t₀-tough graph is hamiltonian. Since a square of a k-connected graph is always k-tough, a proof of this conjecture with t₀ = 2 would imply Fleischner's theorem (the square of a block is hamiltonian). We construct an infinite family of ($\text{3}\text{2}$)-tough nonhamiltonian graphs.     

On the radius of graphs

Let G be any 3-connected graph containing n vertices and r the radius of G. Then the inequality $\text{r <}\text{1}\text{4}\text{n + O(}\text{log}\text{n)}$ is proved. A similar theorem concerning any (2m ?1)-connected graph G can be proved too.     

Infinite subgraphs as matroid circuits

A matroidal family $\text{C}$ is defined to be a collection of graphs such that, for any given graph G, the subgraphs of G isomorphic to a graph in $\text{C}$ satisfy the matroid circuit-axioms. Here matroidal families closed under homeomorphism are considered. A theorem of Simöes-Pereira shows that when only finite connected graphs are allowed as members of $\text{C}$, two matroids arise: the cycle matroid and bicircular matroid. Here this theorem is generalized in two directions: the graphs are allowed to be infinite, and they are allowed to be disconnected. In the first case four structures result and in the second case two infinite families of matroids are obtained. The main theorem concerns the structures resulting when both restrictions are relaxed simultaneously.