ﻻ يوجد ملخص باللغة العربية
The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. A reduced graph $G$ is said to be maximal if any reduced graph containing $G$ as a proper induced subgraph has a higher rank. The main intent of this paper is to present some results on maximal graphs. First, we introduce a characterization of maximal trees (a reduced tree is a maximal tree if it is not a proper subtree of a reduced tree with the same rank). Next, we give a near-complete characterization of maximal `generalized friendship graphs. Finally, we present an enumeration of all maximal graphs with ranks $8$ and $9$. The ranks up to $7$ were already done by Lepovic (1990), Ellingham (1993), and Lazic (2010).
We study the class of all finite directed graphs up to primitive positive constructability. The resulting order has a unique greatest element, namely the graph $P_1$ with one vertex and no edges. The graph $P_1$ has a unique greatest lower bound, nam
We define a zeta function of a graph by using the time evolution matrix of a general coined quantum walk on it, and give a determinant expression for the zeta function of a finite graph. Furthermore, we present a determinant expression for the zeta function of an (infinite) periodic graph.
Posas theorem states that any graph $G$ whose degree sequence $d_1 le ldots le d_n$ satisfies $d_i ge i+1$ for all $i < n/2$ has a Hamilton cycle. This degree condition is best possible. We show that a similar result holds for suitable subgraphs $G$
Let $mathfrak{n}$ be a nonempty, proper, convex subset of $mathbb{C}$. The $mathfrak{n}$-maximal operators are defined as the operators having numerical ranges in $mathfrak{n}$ and are maximal with this property. Typical examples of these are the max
If G is a graph and H is a set of subgraphs of G, then an edge-coloring of G is called H-polychromatic if every graph from H gets all colors present in G on its edges. The H-polychromatic number of G, denoted poly_H(G), is the largest number of color