Diameters of random circulant graphs

The diameter of a graph measures the maximal distance between any pair of vertices. The diameters of many small-world networks, as well as a variety of other random graph models, grow logarithmically in the number of nodes. In contrast, the worst connected networks are cycles whose diameters increase linearly in the number of nodes. In the present study we consider an intermediate class of examples: Cayley graphs of cyclic groups, also known as circulant graphs or multi-loop networks. We show that the diameter of a random circulant 2k-regular graph with n vertices scales as n ^1/k , and establish a limit theorem for the distribution of their diameters. We obtain analogous results for the distribution of the average distance and higher moments.     

Enumeration of Bipartite Self-Complementary Graphs

Let e(m, n), o(m, n), bsc(m, n) be the number of unlabelled bipartite graphs with an even number of edges whose partite sets have m vertices and n vertices, the number of those with an odd number of edges, and the number of unlabelled bipartite self-complementary graphs whose partite sets have m vertices and n vertices, respectively. Then this paper shows that the equality bsc(m, n) = e(m, n) ? o(m, n) holds.     

Skew Hadamard designs and their codes

Skew Hadamard designs (4n – 1, 2n – 1, n – 1) are associated to order 4n skew Hadamard matrices in the natural way. We study the codes spanned by their incidence matrices A and by I + A and show that they are self-dual after extension (resp. extension and augmentation) over fields of characteristic dividing n. Quadratic Residues codes are obtained in the case of the Paley matrix. Results on the p-rank of skew Hadamard designs are rederived in that way. Codes from skew Hadamard designs are classified. An optimal self-dual code over GF(5) is rediscovered in length 20. Six new inequivalent [56, 28, 16] self-dual codes over GF(7) are obtained from skew Hadamard matrices of order 56, improving the only known quadratic double circulant code of length 56 over GF(7).     

Directed graph representation of half-rate additive codes over GF(4)

We show that (n, 2 ⁿ ) additive codes over GF(4) can be represented as directed graphs. This generalizes earlier results on self-dual additive codes over GF(4), which correspond to undirected graphs. Graph representation reduces the complexity of code classification, and enables us to classify additive (n, 2 ⁿ ) codes over GF(4) of length up to 7. From this we also derive classifications of isodual and formally self-dual codes. We introduce new constructions of circulant and bordered circulant directed graph codes, and show that these codes will always be isodual. A computer search of all such codes of length up to 26 reveals that these constructions produce many codes of high minimum distance. In particular, we find new near-extremal formally self-dual codes of length 11 and 13, and isodual codes of length 24, 25, and 26 with better minimum distance than the best known self-dual codes.     

On the harmonious coloring of collections of graphs

The hermonious coloring number of the graph G, HC(G), is the smallest number of colors needed to label the vertices of G such that adjacent vertices received different colors and no two edges are incident with the same color pair. In this paper, we investigate the HC-number of collections of disjoint paths, cycles, complete graphs, and complete bipartite graphs. We determine exact expressions for the HC-number of collections of paths and 4m-cycles. © 1995, John Wiley & Sons, Inc.     

Planar graphs without specific cycles are 2-degenerate

A graph G is k-degenerate if each subgraph of G has a vertex of degree at most k. It is known that every simple planar graph with girth 6, or equivalently without 3-, 4-, and 5-cycles, is 2-degenerate. In this work, we investigate for which k every planar graph without 4-, 6-, … , and 2k-cycles is 2-degenerate. We determine that k is 5 and the result is tight since the truncated dodecahedral graph is a 3-regular planar graph without 4-, 6-, and 8-cycles. As a related result, we also show that every planar graph without 4-, 6-, 9-, and 10-cycles is 2-degenerate.     

Matrices of zeros and ones with fixed row and column sum vectors

Let m and n be positive integers, and let R=(r₁,…,r_m) and S=(s₁,…,s_n) be nonnegative integral vectors. We survey the combinational properties of the set of all m × n matrices of 0's and 1's having r_i1's in row i ands_i 1's in column j. A number of new results are proved. The results can be also be formulated in terms of a set of bipartite graps with bipartition into m and n vertices having degree sequence R and S, respectively. They can also be formulated in terms of the set of hypergraphs with m vertices having degree sequence R and n edges whose cardinalities are given by S.     

Submatrices of non-tree-realizable distance matrices

We deal with distance matrices of real (this means, not necessarily integer) numbers. It is known that a distance matrix D of order n is tree-realizable if and only if all its principal submatrices of order 4 are tree-realizable. We discuss bounds for the number, denoted Q_i(D), of non-tree-realizable principal submatrices of order i ? 4 of a non-tree-realizable distance matrix D of order n?i, and we construct some distance matrices which meet extremal conditions on Q_i(D). Our starting point is a proof that a non-tree-realizable distance matrix of order 5 has at least two non-tree-realizable principal submatrices of order 4. Optimal realizations (by graphs with circuits) of distance matrices which are not tree-realizable are not yet as well known as optimal realizations which are trees. Using as starting point the optimal realization of the (arbitrary) distance matrix of order 4, we investigate optimal realizations of non-tree-realizable distance matrices with the minimum number of non-tree-realizable principal submatrices of order 4.     

Longest cycles in regular graphs

The paper is concerned with the longest cycles in regular three- (or two-) connected graphs. In particular, the following results are proved: (i) every 3-connected k-regular graph on n vertices has a cycle of length at least min(3k, n); (ii) every 2-connected k-regular graph on n vertices, where n < 3k + 4, has a cycle of length at least min(3k, n).     

Path-path Ramsey-type numbers for the complete bipartite graph

For a fixed pair of integers r, s ≥ 2, all positive integers m and n are determined which have the property that if the edges of K_m,n (a complete bipartite graph with parts n and m) are colored with two colors, then there will always exist a path with r vertices in the first color or a path with s vertices in the second color.     

On regular graphs and Hamiltonian circuits,including answers to some questions of Joseph Zaks

A graph is called l-ply Hamiltonian if it admits l edge-disjoint Hamiltonian circuits. The following results are obtained: (1) When n ≥ 3 and 0 ≤ 2l ≤ n there exists an n-connected n-regular graph that is exactly l-ply Hamiltonian. (2) There exist 5-connected 5-regular planar graphs that are not doubly (i.e. 2-ply) Hamiltonian, one with only 132 vertices and another with only three types of face, namely 3-, 4- and 12-gons. (3) There exist 3-connected 5-regular planar graphs, one that is non-Hamiltonian and has only 76 vertices and another that has no Hamiltonian paths and has only 128 vertices. (4) There exist 5-edge-connected 5-regular planar graphs, one that is non-Hamiltonian and has only 176 vertices and another that has no Hamiltonian paths and has only 512 vertices. Result (1) was known in the special cases $\text{l = [}\text{n}\text{2}\text{]}$ (an old result) and l = 0 (due to G. H. J. Meredith, 1973). The special case l = 1 provides a negative answer to question 4 in a recent paper by Joseph Zaks and implies Corollary 1 to Zaks' Theorem 1. Results (2) and (3) involve graphs with considerably fewer vertices (and, in one case, fewer types of face) than Zaks' corresponding graphs and provide partial answers to his questions 1 and 3. Result (4) involves graphs that satisfy a stronger condition than those of Zaks but still have fewer vertices.     

Self-dual codes from circulant matrices

In this paper, two general methods for constructing self-dual codes are presented. These methods use circulant matrices in circulant or bordered circulant structures to construct the suitable generator matrices. The necessary and sufficient conditions, for the generated codes to be self-dual, are provided. Special cases of the proposed methods include the well known “Pure Double Circulant” construction and the “Bordered Double circulant” construction of self-dual codes. As an example, the methods were applied to search for self-dual codes in GF(5). Many new inequivalent self-dual codes with best known distance are found.     

Bounds on the eigenvalues of graphs with cut vertices or edges

In this paper, we characterize the extremal graph having the maximal Laplacian spectral radius among the connected bipartite graphs with n vertices and k cut vertices, and describe the extremal graph having the minimal least eigenvalue of the adjacency matrices of all the connected graphs with n vertices and k cut edges. We also present lower bounds on the least eigenvalue in terms of the number of cut vertices or cut edges and upper bounds on the Laplacian spectral radius in terms of the number of cut vertices.     

Subtotally positive and Monge matrices

A real matrix is called k-subtotally positive if the determinants of all its submatrices of order at most k are positive. We show that for an m × n matrix, only mn inequalities determine such class for every k, 1 ? k ? min(m,n). Spectral properties of square k-subtotally positive matrices are studied. Finally, completion problems for 2-subtotally positive matrices and their additive counterpart, the anti-Monge matrices, are investigated. Since totally positive matrices are 2-subtotally positive as well, the presented necessary conditions for this completion problem are also necessary conditions for totally positive matrices.     

Mutually disjoint t-designs and t-SEEDs from extremal doubly-even self-dual codes

It is known that extremal doubly-even self-dual codes of length \(n\equiv 8\) or \(0\ (\mathrm {mod}\ 24)\) yield 3- or 5-designs respectively. In this paper, by using the generator matrices of bordered double circulant doubly-even self-dual codes, we give 3-(n, k; m)-SEEDs with (n, k, m) \(\in \{(32,8,5), (56,12,9), (56,16,9), (56,24,9), (80,16,52)\}\) . With the aid of computer, we obtain 22 generator matrices of bordered double circulant doubly-even self-dual codes of length 48, which enable us to get 506 mutually disjoint 5-(48, k, \(\lambda \) ) designs for (k, \(\lambda \) )=(12, 8),(16, 1356),(20, 36176). Moreover, this implies 5-(48, k; 506)-SEEDs for \(k=12, 16, 20, 24\) .     

Codes from incidence matrices of graphs

We examine the p-ary codes, for any prime p, from the row span over ${\mathbb {F}_p}$ of |V| × |E| incidence matrices of connected graphs Γ = (V, E), showing that certain properties of the codes can be directly derived from the parameters and properties of the graphs. Using the edge-connectivity of Γ (defined as the minimum number of edges whose removal renders Γ disconnected) we show that, subject to various conditions, the codes from such matrices for a wide range of classes of connected graphs have the property of having dimension |V| or |V| ? 1, minimum weight the minimum degree δ(Γ), and the minimum words the scalar multiples of the rows of the incidence matrix of this weight. We also show that, in the k-regular case, there is a gap in the weight enumerator between k and 2k ? 2 of the binary code, and also for the p-ary code, for any prime p, if Γ is bipartite. We examine also the implications for the binary codes from adjacency matrices of line graphs. Finally we show that the codes of many of these classes of graphs can be used for permutation decoding for full error correction with any information set.     

On bipartite graphs with minimal energy

The energy of a graph is the sum of the absolute values of the eigenvalues of the graph. In a paper [G. Caporossi, D. Cvetkovi, I. Gutman, P. Hansen, Variable neighborhood search for extremal graphs. 2. Finding graphs with external energy, J. Chem. Inf. Comput. Sci. 39 (1999) 984-996] Caporossi et al. conjectured that among all connected graphs G with n≥6 vertices and n−1≤m≤2(n−2) edges, the graphs with minimum energy are the star S_n with m−n+1 additional edges all connected to the same vertices for m≤n+⌊(n−7)/2⌋, and the bipartite graph with two vertices on one side, one of which is connected to all vertices on the other side, otherwise. The conjecture is proved to be true for m=n−1,2(n−2) in the same paper by Caporossi et al. themselves, and for m=n by Hou in [Y. Hou, Unicyclic graphs with minimal energy, J. Math. Chem. 29 (2001) 163-168]. In this paper, we give a complete solution for the second part of the conjecture on bipartite graphs. Moreover, we determine the graph with the second-minimal energy in all connected bipartite graphs with n vertices and edges.     

On the connectivity of bipartite distance-balanced graphs

A connected graph Γ is said to be distance-balanced whenever for any pair of adjacent vertices u,v of Γ the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. In [K. Handa, Bipartite graphs with balanced (a,b)-partitions, Ars Combin.51 (1999), 113-119] Handa asked whether every bipartite distance-balanced graph, that is not a cycle, is 3-connected. In this paper the Handa question is answered in the negative. Moreover, we show that a minimal bipartite distance-balanced graph, that is not a cycle and is not 3-connected, has 18 vertices and is unique. In addition, we give a complete classification of non-3-connected bipartite distance-balanced graphs for which the minimal distance between two vertices in a 2-cut is three. All such graphs are regular and for each k≥3 there exists an infinite family of such graphs which are k-regular.Furthermore, we determine a number of structural properties that a bipartite distance-balanced graph, which is not 3-connected, must have. As an application, we give a positive answer to the Handa question for the subfamily of bipartite strongly distance-balanced graphs.     

On the binary codes with parameters of triply-shortened 1-perfect codes

We study properties of binary codes with parameters close to the parameters of 1-perfect codes. An arbitrary binary (n?=?2 ^m ? 3, 2 ^n-m-1, 4) code C, i.e., a code with parameters of a triply-shortened extended Hamming code, is a cell of an equitable partition of the n-cube into six cells. An arbitrary binary (n?=?2 ^m ? 4, 2 ^n-m , 3) code D, i.e., a code with parameters of a triply-shortened Hamming code, is a cell of an equitable family (but not a partition) with six cells. As a corollary, the codes C and D are completely semiregular; i.e., the weight distribution of such codes depends only on the minimal and maximal codeword weights and the code parameters. Moreover, if D is self-complementary, then it is completely regular. As an intermediate result, we prove, in terms of distance distributions, a general criterion for a partition of the vertices of a graph (from rather general class of graphs, including the distance-regular graphs) to be equitable.     

On the structure of the adjacency matrix of the line digraph of a regular digraph

We show that the adjacency matrix M of the line digraph of a d-regular digraph D on n vertices can be written as M=AB, where the matrix A is the Kronecker product of the all-ones matrix of dimension d with the identity matrix of dimension n and the matrix B is the direct sum of the adjacency matrices of the factors in a dicycle factorization of D.