Nullspace vertex partition in graphs Sciriha, Irene; Mifsud, Xandru; Borg, James L.
Journal of combinatorial optimization,
08/2021, Letnik:
42, Številka:
2
Journal Article
Recenzirano
Odprti dostop
The core vertex set of a graph is an invariant of the graph. It consists of those vertices associated with the non-zero entries of the nullspace vectors of a
{
0
,
1
}
-adjacency matrix. The ...remaining vertices of the graph form the core-forbidden vertex set. For graphs with independent core vertices, such as bipartite minimal configurations and trees, the nullspace induces a well defined three part vertex partition. The parts of this partition are the core vertex set, their neighbours and the remote core-forbidden vertices. The set of the remote core-forbidden vertices are those not adjacent to any core vertex. We show that this set can be removed, leaving the nullity unchanged. For graphs with independent core vertices, we show that the submatrix of the adjacency matrix defining the edges incident to the core vertices determines the nullity of the adjacency matrix. For the efficient allocation of edges in a network graph without altering the nullity of its adjacency matrix, we determine which perturbations make up sufficient conditions for the core vertex set of the adjacency matrix of a graph to be preserved in the process.
λ–Core distance partitions Mifsud, Xandru
Linear algebra and its applications,
03/2021, Letnik:
613
Journal Article
Recenzirano
Odprti dostop
The λ–core vertices of a graph correspond to the non–zero entries of some eigenvector of λ for a universal adjacency matrix U of the graph. We define a partition of the vertex set V based on the ...λ–core vertex set and its neighbourhoods at a distance r, and give a number of results relating the structure of the graph to this partition. For such partitions, we also define an entropic measure for the information content of a graph, related to every distinct eigenvalue λ of U, and discuss its properties and potential applications.
We give results concerning two problems on the recently introduced flip colourings of graphs, a new class of local v. global phenomena. We prove that for \((b, r)\)-flip sequences with \(4 \leq b < r ...< b + 2 \left\lfloor\frac{b+2}{6}\right\rfloor^2\), small constructions of \((b,r)\)-flip graphs on \(O(b+r)\) vertices are possible. Furthermore, we prove that there exists \(k\)-flip sequences \((a_1, \dots, a_k)\) where \(k > 4\), such that \(a_k\) can be arbitrarily large whilst \(a_i\) is constant for \(1 \leq i < \frac{k}{4}\).
We establish a sharp lower-bound for the number of conjugacy classes $k(A_n)$
in the alternating group $A_n$, for $n \geq 3$. Namely, we show that
$k\left(A_n\right) \geq ...\frac{k\left(A_7\right)}{\log_2\left|A_7\right|} \cdot
\log_2\left|A_n\right|$ with equality if, and only if, $n = 7$. The
observations leading towards this result were obtained through a genetic
algorithm developed to search for groups having certain properties.
This paper concerns \((r,c)\)-constant graphs, which are \(r\)-regular graphs in which the subgraph induced by the open neighbourhood of every vertex has precisely \(c\) edges. The family of ...\((r,c)\)-graphs contains vertex-transitive graphs (and in particular Cayley graphs), graphs with constant link (sometimes called locally isomorphic graphs), \((r,b)\)-regular graphs, strongly regular graphs, and much more. This family was recently introduced in arXiv:2312.08777 serving as important tool in constructing flip graphs arXiv:2312.08777, arXiv:2401.02315. In this paper we shall mainly deal with the following: i. Existence and non-existence of \((r, c)\)-planar graphs. We completely determine the cases of existence and non-existence of such graphs and supply the smallest order in the case when they exist. ii. We consider the existence of \((r, c)\)-circulant graphs. We prove that for \(c \equiv 2 \ (\mathrm{mod} \ 3)\) no \((r,c)\)-circulant graph exists and that for \(c \equiv 0, 1 \ (\mathrm{mod} \ 3)\), \(c > 0\) and \(r \geq 6 + \sqrt{\frac{8c - 5}{3}}\) there exists \((r,c)\)-circulant graphs. Moreover for \(c = 0\) and \(r \geq 1\), \((r, 0)\)-circulants exist. iii. We consider the existence and non-existence of small \((r,c)\)-constant graphs, supplying a complete table of the smallest order of graphs we found for \(0 \leq c \leq \binom{r}{2}\) and \(r \leq 6\). We shall also determine all the cases in this range for which \((r,c)\)-constant graphs don't exist. We establish a public database of \((r,c)\)-constant graphs for varying \(r\), \(c\) and order.
The $\lambda$-core vertices of a graph correspond to the non-zero entries of
some eigenvector of $\lambda$ for a universal adjacency matrix $\mathbf{U}$ of
the graph. We define a partition of the ...vertex set $V$ based on the
$\lambda$-core vertex set and its neighbourhoods at a distance $r$, and give a
number of results relating the structure of the graph to this partition. For
such partitions, we also define an entropic measure for the information content
of a graph, related to every distinct eigenvalue $\lambda$ of $\mathbf{U}$, and
discuss its properties and potential applications.
We establish a sharp lower-bound for the number of conjugacy classes \(k(A_n)\) in the alternating group \(A_n\), for \(n \geq 3\). Namely, we show that \(k\left(A_n\right) \geq ...\frac{k\left(A_7\right)}{\log_2\left|A_7\right|} \cdot \log_2\left|A_n\right|\) with equality if, and only if, \(n = 7\). The observations leading towards this result were obtained through a genetic algorithm developed to search for groups having certain properties.
A graph $G$ is defined encapsulating the number theoretic notion of the
Fundamental Theorem of Arithmetic. We then provide a graph theoretic approach
to the fundamental results on the coprimality of ...two natural numbers, through
the use of an adjacency operator $\hat{\mathbf{A}}(G)$. Lastly, these results
are used to give an alternate proof to the known result that there are
infinitely many primes in the natural numbers $\mathbb{N}$.
The \(\lambda\)-core vertices of a graph correspond to the non-zero entries of some eigenvector of \(\lambda\) for a universal adjacency matrix \(\mathbf{U}\) of the graph. We define a partition of ...the vertex set \(V\) based on the \(\lambda\)-core vertex set and its neighbourhoods at a distance \(r\), and give a number of results relating the structure of the graph to this partition. For such partitions, we also define an entropic measure for the information content of a graph, related to every distinct eigenvalue \(\lambda\) of \(\mathbf{U}\), and discuss its properties and potential applications.
PDF
