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


FC1 Graphs and Networks 3
June 11, 2021  12:15 PM
1 - GB Dantzig

Latest news

  • 6/5/21
    Conference abstract book

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.