Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMaximal graphs with respect to rank
111
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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).
rate research
Read More
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, namely the graph $P_2$ with two vertices and one directed edge. Our main result is a complete description of the greatest lower bounds of $P_2$; we call these graphs submaximal. We show that every graph that is not equivalent to $P_1$ and $P_2$ is below one of the submaximal graphs.
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$ of random graphs, i.e. we prove a `resilience version of Posas theorem: if $pn ge C log n$ and the $i$-th vertex degree (ordered increasingly) of $G subseteq G_{n,p}$ is at least $(i+o(n))p$ for all $i<n/2$, then $G$ has a Hamilton cycle. This is essentially best possible and strengthens a resilience version of Diracs theorem obtained by Lee and Sudakov. Chvatals theorem generalises Posas theorem and characterises all degree sequences which ensure the existence of a Hamilton cycle. We show that a natural guess for a resilience version of Chvatals theorem fails to be true. We formulate a conjecture which would repair this guess, and show that the corresponding degree conditions ensure the existence of a perfect matching in any subgraph of $G_{n,p}$ which satisfies these conditions. This provides an asymptotic characterisation of all degree sequences which resiliently guarantee the existence of a perfect matching.
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 maximal symmetric (or accretive or dissipative) operators, the associated to some sesquilinear forms (for instance, to closed sectorial forms), and the generators of some strongly continuous semi-groups of bounded operators. In this paper the $mathfrak{n}$-maximal operators are studied and some characterizations of these in terms of the resolvent set are given.
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 colors in an H-polychromatic coloring. In this paper, poly_H(G) is determined exactly when G is a complete graph and H is the family of all 1-factors. In addition poly_H(G) is found up to an additive constant term when G is a complete graph and H is the family of all 2-factors, or the family of all Hamiltonian cycles.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
