Potentially self-complementary degree sequences

A simple set of conditions is given to determine whether or not a sequence (d₁, …, d_p) is the degree sequence of a self-complementary graph.     

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.     

The convex hull of degree sequences of signed graphs

As shown in [D. Hoffman, H. Jordon, Signed graph factors and degree sequences, J. Graph Theory 52 (2006) 27-36], the degree sequences of signed graphs can be characterized by a system of linear inequalities. The set of all n-tuples satisfying this system of linear inequalities is a polytope P_n. In this paper, we show that P_n is the convex hull of the set of degree sequences of signed graphs of order n. We also determine many properties of P_n, including a characterization of its vertices. The convex hull of imbalance sequences of digraphs is also investigated using the characterization given in [D. Mubayi, T.G. Will, D.B. West, Realizing degree imbalances of directed graphs, Discrete Math. 239 (2001) 147-153].     

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.     

Cycles in self-complementary graphs

Let G be a self-complementary graph of order p ≥ 8. It is shown that for every integer l, 3 ≤ l ≤ p ? 2, G has an l-cycle. Further, if G is hamiltonian, then G is pancyclic.     

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.     

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.     

The spectral radius of bicyclic graphs with prescribed degree sequences

Restricted to the bicyclic graphs with prescribed degree sequences, we determine the (unique) graph with the largest spectral radius with respect to the adjacency matrix.     

The asymptotic number of labeled graphs with given degree sequences

Asymptotics are obtained for the number of n × n symmetric non-negative integer matrices subject to the following constraints: (i) each row sum is specified and bounded, (ii) the entries are bounded, and (iii) a specified “sparse” set of entries must be zero. The result can be interpreted in terms of incidence matrices for labeled graphs.     

Which cospectral graphs have same degree sequences

Two graphs are said to be $L$-cospectral (respectively, $Q$-cospectral) if they have the same (respectively, signless) Laplacian spectra, and a graph $G$ is said to be $L?DS$ (respectively, $Q?DS$) if there does not exist other non-isomorphic graph $H$ such that $H$ and $G$ are $L$-cospectral (respectively, $Q$-cospectral). Let $d_1\left(G\right)\ge d_2\left(G\right)\ge ?\ge d_n\left(G\right)$ be the degree sequence of a graph $G$ with $n$ vertices. In this paper, we prove that except for two exceptions (respectively, the graphs with $d_1\left(G\right)\in \{4,5\}$), if $H$ is $L$-cospectral (respectively, $Q$-cospectral) with a connected graph $G$ and $d_2\left(G\right)=2$, then $H$ has the same degree sequence as $G$. A spider graph is a unicyclic graph obtained by attaching some paths to a common vertex of the cycle. As an application of our result, we show that every spider graph and its complement graph are both $L?DS$, which extends the corresponding results of Haemers et al. (2008), Liu et al. (2011), Zhang et al. (2009) and Yu et al. (2014).     

A simple criterion on degree sequences of graphs

A finite sequence of nonnegative integers is called graphic if the terms in the sequence can be realized as the degrees of vertices of a finite simple graph. We present two new characterizations of graphic sequences. The first of these is similar to a result of Havel-Hakimi, and the second equivalent to a result of Erd?s & Gallai, thus providing a short proof of the latter result. We also show how some known results concerning degree sets and degree sequences follow from our results.     

The signless Laplacian spectral radius of graphs with given degree sequences

In this paper, we investigate the properties of the largest signless Laplacian spectral radius in the set of all simple connected graphs with a given degree sequence. These results are used to characterize the unicyclic graphs that have the largest signless Laplacian spectral radius for a given unicyclic graphic degree sequence. Moreover, all extremal unicyclic graphs having the largest signless Laplacian spectral radius are obtained in the sets of all unicyclic graphs of order n with a specified number of leaves or maximum degree or independence number or matching number.     

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.     

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.     

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.     

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.