Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCharacteristic Power Series of Graph Limits
197
0
0.0
(
0
)
Added by
Joshua N. Cooper
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Authors
Joshua N. Cooper
Ask ChatGPT about the research
No Arabic abstract
In this note, we show how to obtain a characteristic power series of graphons -- infinite limits of dense graphs -- as the limit of normalized reciprocal characteristic polynomials. This leads to a new characterization of graph quasi-randomness and another perspective on spectral theory for graphons, a complete description of the function in terms of the spectrum of the graphon as a self-adjoint kernel operator. Interestingly, while we apply a standard regularization to classical determinants, it is unclear how necessary this is.
rate research
Read More
Graphons are analytic objects representing limits of convergent sequences of graphs. Lovasz and Szegedy conjectured that every finitely forcible graphon, i.e. any graphon determined by finitely many graph densities, has a simple structure. In particular, one of their conjectures would imply that every finitely forcible graphon has a weak $varepsilon$-regular partition with the number of parts bounded by a polynomial in $varepsilon^{-1}$. We construct a finitely forcible graphon $W$ such that the number of parts in any weak $varepsilon$-regular partition of $W$ is at least exponential in $varepsilon^{-2}/2^{5log^*varepsilon^{-2}}$. This bound almost matches the known upper bound for graphs and, in a certain sense, is the best possible for graphons.
This book is based on Graph Theory courses taught by P.A. Petrosyan, V.V. Mkrtchyan and R.R. Kamalian at Yerevan State University.
Let $G$ be a graph with $n$ vertices, and let $A(G)$ and $D(G)$ denote respectively the adjacency matrix and the degree matrix of $G$. Define $$ A_{alpha}(G)=alpha D(G)+(1-alpha)A(G) $$ for any real $alphain [0,1]$. The $A_{alpha}$-characteristic polynomial of $G$ is defined to be $$ det(xI_n-A_{alpha}(G))=sum_jc_{alpha j}(G)x^{n-j}, $$ where $det(*)$ denotes the determinant of $*$, and $I_n$ is the identity matrix of size $n$. The $A_{alpha}$-spectrum of $G$ consists of all roots of the $A_{alpha}$-characteristic polynomial of $G$. A graph $G$ is said to be determined by its $A_{alpha}$-spectrum if all graphs having the same $A_{alpha}$-spectrum as $G$ are isomorphic to $G$. In this paper, we first formulate the first four coefficients $c_{alpha 0}(G)$, $c_{alpha 1}(G)$, $c_{alpha 2}(G)$ and $c_{alpha 3}(G)$ of the $A_{alpha}$-characteristic polynomial of $G$. And then, we observe that $A_{alpha}$-spectra are much efficient for us to distinguish graphs, by enumerating the $A_{alpha}$-characteristic polynomials for all graphs on at most 10 vertices. To verify this observation, we characterize some graphs determined by their $A_{alpha}$-spectra.
In 1971, Tutte wrote in an article that it is tempting to conjecture that every 3-connected bipartite cubic graph is hamiltonian. Motivated by this remark, Horton constructed a counterexample on 96 vertices. In a sequence of articles by different authors several smaller counterexamples were presented. The smallest of these graphs is a graph on 50 vertices which was discovered independently by Georges and Kelmans. In this article we show that there is no smaller counterexample. As all non-hamiltonian 3-connected bipartite cubic graphs in the literature have cyclic 4-cuts -- even if they have girth 6 -- it is natural to ask whether this is a necessary prerequisite. In this article we answer this question in the negative and give a construction of an infinite family of non-hamiltonian cyclically 5-connected bipartite cubic graphs. In 1969, Barnette gave a weaker version of the conjecture stating that 3-connected planar bipartite cubic graphs are hamiltonian. We show that Barnettes conjecture is true up to at least 90 vertices. We also report that a search of small non-hamiltonian 3-connected bipartite cubic graphs did not find any with genus less than 4.
The localization game is a pursuit-evasion game analogous to Cops and Robbers, where the robber is invisible and the cops send distance probes in an attempt to identify the location of the robber. We present a novel graph parameter called the capture time, which measures how long the localization game lasts assuming optimal play. We conjecture that the capture time is linear in the order of the graph, and show that the conjecture holds for graph families such as trees and interval graphs. We study bounds on the capture time for trees and its monotone property on induced subgraphs of trees and more general graphs. We give upper bounds for the capture time on the incidence graphs of projective planes. We finish with new bounds on the localization number and capture time using treewidth.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
