E. Prisner in his book Graph Dynamics defines the $k$-path-step operator on the class of finite graphs. The $k$-path-step operator (for a positive integer $k$) is the operator $S_k^{\text{'}}$ which to every finite graph $G$ assigns the graph $S_k^{\text{'}}\left(G\right)$ which has the same vertex set as $G$ and in which two vertices are adjacent if and only if there exists a path of length $k$ in $G$ connecting them. In the paper the trees and the unicyclic graphs fixed in the operator $S_3^{\text{'}}$ are studied.

Let G be a nontrivial connected graph with an edge-coloring c : E(G) → {1, 2, . . . , q}, q ∈ ℕ, where adjacent edges may be colored the same. A tree T in G is a rainbow tree if no two edges of T receive the same color. For a vertex subset S ⊆ V (G), a tree that connects S in G is called an S-tree. The minimum number of colors that are needed in an edge-coloring of G such that there is a rainbow S-tree for each k-subset S of V (G) is called the k-rainbow index of G, denoted by rxk(G). In this paper,...

We take as given a real symmetric matrix A, whose graph is a tree T, and the eigenvalues of A, with their multiplicities. Each edge of T may then be classified in one of four categories, based upon the change in multiplicity of a particular eigenvalue, when the edge is removed (i.e. the corresponding entry of A is replaced by 0).We show a necessary and suficient condition for each possible classification of an edge. A special relationship is observed among 2-Parter edges, Parter edges and singly...

Suppose a graph $G=(V,E)$ whose edges are partitioned into $p$ disjoint categories (colors) is given. In the color-balanced spanning tree problem a spanning tree is looked for that minimizes the variability in the number of edges from different categories. We show that polynomiality of this problem depends on the number $p$ of categories and present some polynomial algorithm.

We prove a converse of the well-known Kelly’s Lemma. This motivates the introduction of the general notions of $𝒦$-table, $𝒦$-congruence and control-class.

The article studies the cubic mapping graph $\Gamma \left(n\right)$ of ${\mathbb{Z}}_n\left[\mathrm{i}\right]$, the ring of Gaussian integers modulo $n$. For each positive integer $n>1$, the number of fixed points and the in-degree of the elements $\overline{1}$ and $\overline{0}$ in $\Gamma \left(n\right)$ are found. Moreover, complete characterizations in terms of $n$ are given in which ${\Gamma }_2\left(n\right)$ is semiregular, where ${\Gamma }_2\left(n\right)$ is induced by all the zero-divisors of ${\mathbb{Z}}_n\left[\mathrm{i}\right]$.

In 1966, Cummins introduced the “tree graph”: the tree graph T(G) of a graph G (possibly infinite) has all its spanning trees as vertices, and distinct such trees correspond to adjacent vertices if they differ in just one edge, i.e., two spanning trees T1 and T2 are adjacent if T2 = T1 − e + f for some edges e ∈ T1 and f ∉ T1. The tree graph of a connected graph need not be connected. To obviate this difficulty we define the “forest graph”: let G be a labeled graph of order α, finite or infinite,...

For a finite commutative ring $R$ and a positive integer $k⩾2$, we construct an iteration digraph $G(R,k)$ whose vertex set is $R$ and for which there is a directed edge from $a\in R$ to $b\in R$ if $b=a^k$. Let $R=R_1\oplus ...\oplus R_s$, where $s>1$ and $R_i$ is a finite commutative local ring for $i\in \{1,...,s\}$. Let $N$ be a subset of $\{R_1,\cdots ,R_s\}$ (it is possible that $N$ is the empty set $\varnothing$). We define the fundamental constituents $G_N^{*}(R,k)$ of $G(R,k)$ induced by the vertices which are of the form $\{(a_1,\cdots ,a_s)\in R:a_i\in \mathrm{D}\left(R_i\right)$ if $R_i\in N$, otherwise $a_i\in \mathrm{U}\left(R_i\right),i=1,...,s\},$ where U$\left(R\right)$ denotes the unit group of $R$ and D$\left(R\right)$ denotes the zero-divisor set of $R$. We investigate...

The leafage l(G) of a chordal graph G is the minimum number of leaves of a tree in which G has an intersection representation by subtrees. We obtain upper and lower bounds on l(G) and compute it on special classes. The maximum of l(G) on n-vertex graphs is n - lg n - 1/2 lg lg n + O(1). The proper leafage l*(G) is the minimum number of leaves when no subtree may contain another; we obtain upper and lower bounds on l*(G). Leafage equals proper leafage on claw-free chordal graphs. We use asteroidal...

The so-called Lifted Root Number Conjecture is a strengthening of Chinburg’s $\Omega \left(3\right)$- conjecture for Galois extensions $K/F$ of number fields. It is certainly more difficult than the $\Omega \left(3\right)$-localization. Following the lead of Ritter and Weiss, we prove the Lifted Root Number Conjecture for the case that $F=\mathbb{Q}$ and the degree of $K/F$ is an odd prime, with another small restriction on ramification. The very explicit calculations with cyclotomic units use trees and some classical combinatorics for bookkeeping. An important...