Open Journal of Discrete Applied Mathematics (ODAM)

This furthers the notions of parametric equivalence, isomorphism and uniqueness in graphs. Results for certain cycle related graphs are presented. Avenues for further research are also suggested.

The Kolakoski sequence $S$ is the unique element of \(\left\lbrace 1,2 \right\rbrace^{\omega}\) starting with 1 and coinciding with its own run length encoding. We use the parity of the lengths of particular subclasses of initial words of \(S\) as a unifying tool to address the links between the main open questions – recurrence, mirror/reversal invariance and asymptotic density of digits. In particular we prove that recurrence implies reversal invariance, and give sufficient conditions which would imply that the density of 1s is \(\frac{1}{2}\).

The energy of a graph is the sum of absolute values of its eigenvalues. The nullity of a graph is the algebraic multiplicity of number zero in its spectrum. Empirical facts indicate that graph energy decreases with increasing nullity, but proving this property is difficult. In this paper, a method is elaborated by means of which the effect of nullity on graph energy can be quantitatively estimated.

This short paper introduces the notions of parametric equivalence, isomorphism and uniqueness in graphs. Results for paths, cycles and certain categories (or types) of trees with regards to minimum confluence sets are presented.

A variation of Dyck paths allows for down-steps of arbitrary length, not just one. Credits for this invention are given to Emeric Deutsch. Surprisingly, the enumeration of them is somewhat akin to the analysis of Motzkin-paths; the last section contains a bijection.

In this paper we prove that the dominator chromatic number of every oriented tree is invariant under reversal of orientation. In addition to this marquee result, we also prove the exact dominator chromatic number for arborescences and anti-arborescences as well as bounds on other orientations of oft studied tree topologies including generalized stars and caterpillars.

The recently introduced class of vertex-degree-based molecular structure descriptors, called Sombor indices (\(SO\)), are examined and a few of their basic properties established. Simple lower and upper bounds for \(SO\) are determined. It is shown that any vertex–degree–based descriptor can be viewed as a special case of a Sombor-type index.

This paper furthers the study on a new graph parameter called the degree affinity number. The degree affinity number of a graph \(G\) is obtained by iteratively constructing graphs, \(G_1,G_2,\dots,G_k\) of increased size by adding a maximal number of edges between distinct pairs of distinct vertices of equal degree. Preliminary results for certain \(2\)-regular graphs are presented.

The inverse degree of a graph was defined as the sum of the inverses of the degrees of the vertices. In this paper, we focus on finding sufficient conditions in terms of the inverse degree for a graph to be \(k\)-path-coverable, \(k\)-edge-hamiltonian, Hamilton-connected and traceable, respectively. The results obtained are not dropped.

Let \(G\) be a simple and finite graph. A graph is said to be decomposed into subgraphs \(H_1\) and \(H_2\) which is denoted by \(G= H_1 \oplus H_2\), if \(G\) is the edge disjoint union of \(H_1\) and \(H_2\). If \(G= H_1 \oplus H_2 \oplus \cdots \oplus H_k\), where \(H_1\), \(H_2\), …, \(H_k\) are all isomorphic to \(H\), then \(G\) is said to be \(H\)-decomposable. Furthermore, if \(H\) is a cycle of length \(m\) then we say that \(G\) is \(C_m\)-decomposable and this can be written as \(C_m|G\). Where \(G\times H\) denotes the tensor product of graphs \(G\) and \(H\), in this paper, we prove that the necessary conditions for the existence of \(C_6\)-decomposition of \(K_m \times K_n\) are sufficient. Using these conditions it can be shown that every even regular complete multipartite graph \(G\) is \(C_6\)-decomposable if the number of edges of \(G\) is divisible by \(6\).