The polynomial reconstruction problem: The first 50 years

The problem of reconstructing the characteristic polynomial of a graph of order at least 3 from the collection of characteristic polynomials of its vertex-deleted subgraphs was posed by Cvetkovi? in 1973 as a spectral counter part to the well-known Ulam's reconstruction conjecture. Over the last 50 years, this problem has received notable attention, many positive results have been obtained, but in the general case the problem is still unresolved. In particular, no counter example is found in literature. In this expository paper we survey classical and some more recent results concerning the polynomial reconstruction problem, discuss some related problems, variations and generalizations.     

Classroom note: Using the binomial series to prove the arithmetic mean–geometric mean inequality

In 1968, Leon Gerber compared (1 + x) ^a to its kth partial sum as a binomial series. His result is stated and, as an application of this result, a proof of the arithmetic mean–geometric mean inequality is presented.     

Peptide Property Modeling by Cluj Indices

Abstract

The novel Cluj property indices are used for modeling the biological properties of dipeptides: the ACE inhibition activity of a set of 58 dipeptides and the bitter tasting activity of a set of 48 dipeptides, taken from the literature. The results are compared to those reported in some previous works.     

A class of finite groups with complete character degree graphs

In this paper, we construct a new class of finite groups whose common divisor graphs are complete graphs, while there is no prime dividing all the nontrivial degrees.     

Bipartite flocking for multi-agent systems

This paper addresses the bipartite flock control problem where a multi-agent system splits into two clusters upon internal or external excitations. Using structurally balanced signed graph theory, LaSalle’s invariance principle and Barbalat’s Lemma, we prove that the proposed algorithm guarantees a bipartite flocking behavior. In each of the two disjoint clusters, all individuals move with the same direction. Meanwhile, every pair of agents in different clusters moves with opposite directions. Moreover, all agents in the two separated clusters approach a common velocity magnitude, and collision avoidance among all agents is ensured as well. Finally, the proposed bipartite flock control method is examined by numerical simulations. The bipartite flocking motion addressed by this paper has its references in both natural collective motions and human group behaviors such as predator–prey and panic escaping scenarios.     

Highly edge-connected factors using given lists on degrees

Let G be a 2k-edge-connected graph with and let for every . A spanning subgraph F of G is called an L-factor, if for every . In this article, we show that if for every , then G has a k-edge-connected L-factor. We also show that if and for every , then G has a k-edge-connected L-factor.     

On a family of highly regular graphs by Brouwer,Ivanov, and Klin

Highly regular graphs for which not all regularities are explainable by symmetries are fascinating creatures. Some of them like, e.g., the line graph of W. Kantor’s non-classical $GQ(5^2,5)$, are stumbling stones for existing implementations of graph isomorphism tests. They appear to be extremely rare and even once constructed it is difficult to prove their high regularity. Yet some of them, like the McLaughlin graph on 275 vertices and Ivanov’s graph on 256 vertices are of profound beauty. This alone makes it an attractive goal to strive for their complete classification or, failing this, at least to get a deep understanding of them. Recently, one of the authors discovered new methods for proving high regularity of graphs. Using these techniques, in this paper we study a classical family of strongly regular graphs, originally discovered by A.E. Brouwer, A.V. Ivanov, and M.H. Klin in the late 80s. We analyse their symmetries and show that they are $(3,5)$-regular but not 2-homogeneous. Thus we promote these graphs to the distinguished club of highly regular graphs with few symmetries.     

Ends,tangles and critical vertex sets

We show that an arbitrary infinite graph G can be compactified by its ends plus its critical vertex sets, where a finite set X of vertices of an infinite graph is critical if its deletion leaves some infinitely many components each with neighbourhood precisely equal to X. We further provide a concrete separation system whose ?₀‐tangles are precisely the ends plus critical vertex sets. Our tangle compactification is a quotient of Diestel's (denoted by ), and both use tangles to compactify a graph in much the same way as the ends of a locally finite and connected graph compactify it in its Freudenthal compactification. Finally, generalising both Diestel's construction of and our construction of , we show that G can be compactified by every inverse limit of compactifications of the sets of components obtained by deleting a finite set of vertices. Diestel's is the finest such compactification, and our is the coarsest one. Both coincide if and only if all tangles are ends. This answers two questions of Diestel.