P. Wawrzyniak, P. Formanowicz
The classical graph realization is a decision problem checking if a finite sequence of positive numbers can construct a graph, where degrees of nodes match the input sequence. This problem is related to many real problems, such as the design of reliable networks or analysis of biological networks. One such problem is testing the ability of molecular graphs construction basing on mass spectrometry data.
As a model of chemical compounds, the molecular graphs bring some changes to the classical realization problem. In this case, the graph is a model of a single molecule, so we limit only to the connected graphs. The bonds in a chemical compound can be single or multiple, so we have to consider both graphs and multigraphs. Finally, the vertices represent the atoms, and the vertices' degrees match the valency of the atom. Because not each atom has a single valency, we cannot limit it to the single value in the input sequence.
The described modification brings us to the definition of a new problem is, i.e., sequence of sets of positive integers S=(D1, …, Dn) graphic? Sequence S is called graphic when there exists such graph G, whose vertices v1, …, vn have degrees from sets D1, …, Dn.
Keywords: graphical sequences, molecular graphs
Scheduled
FC1 Graphs and Networks 3
June 11, 2021 12:15 PM
1 - GB Dantzig
