Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAsymptotic Spectral Distributions of Distance $k$-Graphs of Cartesian Product Graphs
149
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $G$ be a finite connected graph on two or more vertices and $G^{[N,k]}$ the distance $k$-graph of the $N$-fold Cartesian power of $G$. For a fixed $kge1$, we obtain explicitly the large $N$ limit of the spectral distribution (the eigenvalue distribution of the adjacency matrix) of $G^{[N,k]}$. The limit distribution is described in terms of the Hermite polynomials. The proof is based on asymptotic combinatorics along with quantum probability theory.
rate research
Read More
A graph $G$ is a $k$-prime product distance graph if its vertices can be labeled with distinct integers such that for any two adjacent vertices, the difference of their labels is the product of at most $k$ primes. A graph has prime product number $ppn(G)=k$ if it is a $k$-prime product graph but not a $(k-1)$-prime product graph. Similarly, $G$ is a prime $k$th-power graph (respectively, strict prime $k$th-power graph) if its vertices can be labeled with distinct integers such that for any two adjacent vertices, the difference of their labels is the $j$th power of a prime, for $j leq k$ (respectively, the $k$th power of a prime exactly). We prove that $ppn(K_n) = lceil log_2(n)rceil - 1$, and for a nonempty $k$-chromatic graph $G$, $ppn(G) = lceil log_2(k)rceil - 1$ or $ppn(G) = lceil log_2(k)rceil$. We determine $ppn(G)$ for all complete bipartite, 3-partite, and 4-partite graphs. We prove that $K_n$ is a prime $k$th-power graph if and only if $n < 7$, and we determine conditions on cycles and outerplanar graphs $G$ for which $G$ is a strict prime $k$th-power graph. We find connections between prime product and prime power distance graphs and the Twin Prime Conjecture, the Green-Tao Theorem, and Fermats Last Theorem.
We study the spectrum of a random multigraph with a degree sequence ${bf D}_n=(D_i)_{i=1}^n$ and average degree $1 ll omega_n ll n$, generated by the configuration model, and also the spectrum of the analogous random simple graph. We show that, when the empirical spectral distribution (ESD) of $omega_n^{-1} {bf D}_n $ converges weakly to a limit $ u$, under mild moment assumptions (e.g., $D_i/omega_n$ are i.i.d. with a finite second moment), the ESD of the normalized adjacency matrix converges in probability to $ uboxtimes sigma_{rm sc}$, the free multiplicative convolution of $ u$ with the semicircle law. Relating this limit with a variant of the Marchenko--Pastur law yields the continuity of its density (away from zero), and an effective procedure for determining its support. Our proof of convergence is based on a coupling between the random simple graph and multigraph with the same degrees, which might be of independent interest. We further construct and rely on a coupling of the multigraph to an inhomogeneous ErdH{o}s-Renyi graph with the target ESD, using three intermediate random graphs, with a negligible fraction of edges modified in each step.
The present paper presents two new approaches to Fourier series and spectral analysis of singular measures.
Let $G=(V,E)$ be a graph and $Gamma $ an Abelian group both of order $n$. A $Gamma$-distance magic labeling of $G$ is a bijection $ell colon Vrightarrow Gamma $ for which there exists $mu in Gamma $ such that $% sum_{xin N(v)}ell (x)=mu $ for all $vin V$, where $N(v)$ is the neighborhood of $v$. Froncek %(cite{ref_CicAus}) showed that the Cartesian product $C_m square C_n$, $m, ngeq3$ is a $mathbb{Z}_{mn}$-distance magic graph if and only if $mn$ is even. It is also known that if $mn$ is even then $C_m square C_n$ has $mathbb{Z}_{alpha}times mathcal{A}$-magic labeling for any $alpha equiv 0 pmod {{rm lcm}(m,n)}$ and any Abelian group $mathcal{A}$ of order $mn/alpha$. %cite{ref_CicAus} However, the full characterization of group distance magic Cartesian product of two cycles is still unknown. In the paper we make progress towards the complete solution this problem by proving some necessary conditions. We further prove that for $n$ even the graph $C_{n}square C_{n}$ has a $Gamma$-distance magic labeling for any Abelian group $Gamma$ of order $n^{2}$. Moreover we show that if $m eq n$, then there does not exist a $(mathbb{Z}_2)^{m+n}$-distance magic labeling of the Cartesian product $C_{2^m} square C_{2^{n}}$. We also give necessary and sufficient condition for $C_{m} square C_{n}$ with $gcd(m,n)=1$ to be $Gamma$-distance magic.
The relation between Hamiltonicity and toughness of a graph is a long standing research problem. The paper studies the Hamiltonicity of the Cartesian product graph $G_1square G_2$ of graphs $G_1$ and $G_2$ satisfying that $G_1$ is traceable and $G_2$ is connected with a path factor. Let Pn be the path of order $n$ and $H$ be a connected bipartite graph. With certain requirements of $n$, we show that the following three statements are equivalent: (i) $P_nsquare H$ is Hamiltonian; (ii) $P_nsquare H$ is $1$-tough; and (iii) $H$ has a path factor.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
