Combinatorics and Graph Theory

1906 Submissions

[4] viXra:1906.0502 [pdf] submitted on 2019-06-27 07:21:45

The Construction of Cospectral Graphs with Respect to the Generalized Adjacency Matrix

Authors: Daria Grushka, Viktoriia Lebid
Comments: 4 Pages. Text in Ukrainian. Mohyla Mathematical Journal, Vol 1 (2018)

Spectral graph theory uses the eigenvalues of matrices associated with a graph to determine the structural properties of the graph. The spectrum of the generalized adjacency matrix is considered in the paper. Graphs with the same spectrum are called cospectral. Is every graph uniquely determined by its spectrum (DS for short)? This question goes back for about half a century, and originates from chemistry. In 1956 Gunthard and Primas raised the question in a paper that related the theory of graph spectra to Huckel’s theory. At that time it was believed that every graph is determined by the spectrum, until in 1957 Collatz and Sinogowitz presented a pair of cospectral trees. In 1967 Schwenk proved that for almost all trees there is another tree with the same spectrum. Such a statement is neither proved nor refuted for the class of graphs in general. Till now, computational experiments were done on the set of all graphs on up to 12 vertices by Haemers. Computer enumerations for small n show that up to 10 vertices the fraction of graphs that are DS decreases, but for n = 11 and n = 12 it increases again. We consider the construction of the cospectral graphs called GM-switching for graph G taking the cycle C2n and adjoining a vertex v adjacent to half the vertices of C2n. For these graphs we determine the pairs of cospectral nonisomorphic graphs for small n. It is an operation on graphs that leaves the spectrum of the generalized adjacency matrix invariant. It turns out that for the enumerated cases a large part of all cospectral graphs comes from GM switching, and that the fraction of graphs on n vertices with a cospectral mate starts to decrease at some value of n < 11 (depending on the matrix). Since the fraction of cospectral graphs on n vertices constructible by GM switching tends to 0 if n → ∞, the present data give some indication that possibly almost no graph has a cospectral mate. Haemers and Spence derived asymptotic lower bounds for the number of graphs with a cospectral mate from GM switching.
Category: Combinatorics and Graph Theory

[3] viXra:1906.0501 [pdf] replaced on 2019-07-22 12:27:42

Solving the N_1 X N_2 X N_3 Points Problem for N_3 < 6

Authors: Marco Ripà
Comments: 12 Pages.

In this paper, we show enhanced upper bounds of the nontrivial n_1 × n_2 × n_3 points problem for every n_1 ≤ n_2 ≤ n_3 < 6. We present new patterns that drastically improve the previously known algorithms for finding minimum-link covering paths, solving completely a few cases (e.g., n_1 = n_2 = 3 and n_3 = 4).
Category: Combinatorics and Graph Theory

[2] viXra:1906.0350 [pdf] submitted on 2019-06-20 03:54:55

On the Coloring of Graphs Formed by Cliques Sharing at Most One Common Vertex

Authors: Prajnanaswaroopa S, J Geetha, K Somasundaram
Comments: 3 Pages.

In this short note, we give a coloring procedure for graphs which consist of cliques sharing at most one point
Category: Combinatorics and Graph Theory

[1] viXra:1906.0031 [pdf] submitted on 2019-06-03 12:10:14

Die Würfelschlange

Authors: Henning Thielemann
Comments: 5 Pages. Language: German

The dice sequence The dice sequence is an adaption of Kruskal's card trick to dice. We compute precise and approximated probabilities that the trick works. The adaption to dice simplifies the problem considerably because the probabilities of the dice rolls are independent. Initially I wrote the text for Wikipedia but in order to meet Wikipedia's exclusion of original research I wrote up this paper.
Category: Combinatorics and Graph Theory