Triangles in self-complementary graphs

It is shown that the number of triangles in a self-complementary graph with N vertices is at least $\text{N(N ? 2)(N ? 4)}\text{48}$ if N ≡ 0 (mod 4) and at least $\text{N(N ? 1)(N ? 5)}\text{48}$ if N ≡ 1 (mod 4), and that this minimum number can be achieved.     

Equienergetic self-complementary graphs

In this paper equienergetic self-complementary graphs on p vertices for every p = 4k, k ⩾ 2 and p = 24t + 1, t ⩾ 3 are constructed.     

On almost self-complementary graphs

A graph is called almost self-complementary if it is isomorphic to one of its almost complements X^c-I, where X^c denotes the complement of X and I a perfect matching (1-factor) in X^c. Almost self-complementary circulant graphs were first studied by Dobson and Šajna [Almost self-complementary circulant graphs, Discrete Math. 278 (2004) 23-44]. In this paper we investigate some of the properties and constructions of general almost self-complementary graphs. In particular, we give necessary and sufficient conditions on the order of an almost self-complementary regular graph, and construct infinite families of almost self-complementary regular graphs, almost self-complementary vertex-transitive graphs, and non-cyclically almost self-complementary circulant graphs.     

On separable self-complementary graphs

In this paper, we describe the structure of separable self-complementary graphs.     

On regular self-complementary graphs

A regular self-complementary graph is presented which has no complementing permutation consisting solely of cycles of length four. This answers one of Kotzig's questions.     

Hamiltonian arcs in infinite self-complementary graphs

An infinite self-complementary (s.c.) graph is quasi-locally-finite if, for each vertex ξ, either the number of vertices adjacent to ξ is finite or the number of vertices not adjacent to ξ is finite. We prove that every quasi-locally-finite s.c. graph has a spanning subgraph consisting of two 1-way infinite arcs, and give an example of a countable s.c. graph (not quasi-locally-finite) which requires infinitely many 1-way infinite arcs for a spanning subgraph.     

More on almost self-complementary graphs

A graph X is called almost self-complementary if it is isomorphic to one of its almost complements , where denotes the complement of X and I a perfect matching (1-factor) in . If I is a perfect matching in and is an isomorphism, then the graph X is said to be fairly almost self-complementary if φ preserves I setwise, and unfairly almost self-complementary if it does not.In this paper we construct connected graphs of all possible orders that are fairly and unfairly almost self-complementary, fairly but not unfairly almost self-complementary, and unfairly but not fairly almost self-complementary, respectively, as well as regular graphs of all possible orders that are fairly and unfairly almost self-complementary.Two perfect matchings I and J in are said to be X-non-isomorphic if no isomorphism from X+I to X+J induces an automorphism of X. We give a constructive proof to show that there exists a graph X that is almost self-complementary with respect to two X-non-isomorphic perfect matchings for every even order greater than or equal to four.     

Sylow subgraphs in self-complementary vertex transitive graphs

A graph is self-complementary if it is isomorphic to its complement. A graph is vertex transitive if for each choice of vertices u and $v$ there is an automorphism that carries the vertex u to $v$. The number of vertices in a self-complementary vertex-transitive graph must necessarily be congruent to 1 mod 4. However, Muzychuk has shown that if $p^m$ is the largest power of a prime p dividing the order of a self-complementary vertex-transitive graph, then $p^m$ must individually be congruent to 1 mod 4. This is accomplished by establishing the existence of a self-complementary vertex transitive subgraph of order $p^m$, a result reminiscent of the Sylow theorems. This article is a self-contained survey, culminating with a detailed proof of Muzychuk's result.     

The degree sequences of self-complementary graphs

Known necessary conditions for realization of a sequence of integers as the degrees of a self-complementary graph are shown to be sufficient. An algorithm for constructing a realization of such a sequence as degrees of such a graph is illustrated by an example.     

Cycles in weighted graphs

A weighted graph is one in which each edgee is assigned a nonnegative numberw(e), called the weight ofe. The weightw(G) of a weighted graphG is the sum of the weights of its edges. In this paper, we prove, as conjectured in [2], that every 2-edge-connected weighted graph onn vertices contains a cycle of weight at least 2w(G)/(n–1). Furthermore, we completely characterize the 2-edge-connected weighted graphs onn vertices that contain no cycle of weight more than 2w(G)/(n–1). This generalizes, to weighted graphs, a classical result of Erds and Gallai [4].     

Cycles in bipartite graphs

For k an integer, let G(a, b, k) denote a simple bipartite graph with bipartition (A, B) where |A| = a ≥ 2, |B| = b ≥ k ≥ 2, and each vertex of A has degree at least k. We prove two results concerning the existence of cycles in G(a, b, k).     

Characterization of self-complementary graphs with 2-factors

Let G be a self-complementary graph (s.c.) and π its degree sequence. Then G has a 2-factor if and only if π - 2 is graphic. This is achieved by obtaining a structure theorem regarding s.c. graphs without a 2-factor. Another interesting corollary of the structure theorem is that if G is a s.c. graph of order p?8 with minimum degree at least $\text{p}\text{4}$, then G has a 2-factor and the result is the best possible.     

Rao's conjecture on self-complementary graphs with K-factors

Rao posed the following conjecture, “Let G be a self-complementary graph of order p, π = (d₁ … dp) be its degree sequence. Then G has a k-factor if and only if π ? k, = (d1 ? k, … dP ? k) is graphical.” We construct a family of counterexamples for this conjecture for every k ? 3.     

Cycles in 2-connected graphs

Let be a class of graphs on n vertices. For an integer c, let be the smallest integer such that if G is a graph in with more than edges, then G contains a cycle of length more than c. A classical result of Erdös and Gallai is that if is the class of all simple graphs on n vertices, then . The result is best possible when n-1 is divisible by c-1, in view of the graph consisting of copies of K_c all having exactly one vertex in common. Woodall improved the result by giving best possible bounds for the remaining cases when n-1 is not divisible by c-1, and conjectured that if is the class of all 2-connected simple graphs on n vertices, thenwhere , 2tc/2, is the number of edges in the graph obtained from K_c+1-t by adding n-(c+1-t) isolated vertices each joined to the same t vertices of K_c+1-t. By using a result of Woodall together with an edge-switching technique, we confirm Woodall's conjecture in this paper.     

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)}$.     

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).     

Cycles in graphs and functional inequalities

Translated from Matematicheskie Zametki, Vol. 46, No. 5, pp. 72–79, November, 1989.