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...

The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree, M1, was understood fully (froma combinatorial perspective) by C.R. Johnson, A. Leal-Duarte (Linear Algebra and Multilinear Algebra 46 (1999) 139-144). Among the possible multiplicity lists for the eigenvalues of Hermitian matrices whose graph is a tree, we focus upon M2, the maximum value of the sum of the two largest multiplicities when the largest multiplicity is M1. Upper and lower bounds are given for M2. Using a combinatorial...

We study upper bounds on the length functional along contractions of loops in Riemannian disks of bounded diameter and circumference. By constructing metrics adapted to imbedded trees of increasing complexity, we reduce the nonexistence of such upper bounds to the study of a topological invariant of imbedded finite trees. This invariant is related to the complexity of the binary representation of integers. It is also related to lower bounds on the number of points in level sets of a real-valued...