ترغب بنشر مسار تعليمي؟ اضغط هنا

Spectra of subdivision-vertex join and subdivision-edge join of two graphs

105   0   0.0 ( 0 )
 نشر من قبل Xiaogang Liu
 تاريخ النشر 2012
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

The subdivision graph $mathcal{S}(G)$ of a graph $G$ is the graph obtained by inserting a new vertex into every edge of $G$. Let $G_1$ and $G_2$ be two vertex disjoint graphs. The emph{subdivision-vertex join} of $G_1$ and $G_2$, denoted by $G_1dot{vee}G_2$, is the graph obtained from $mathcal{S}(G_1)$ and $G_2$ by joining every vertex of $V(G_1)$ with every vertex of $V(G_2)$. The emph{subdivision-edge join} of $G_1$ and $G_2$, denoted by $G_1underline{vee}G_2$, is the graph obtained from $mathcal{S}(G_1)$ and $G_2$ by joining every vertex of $I(G_1)$ with every vertex of $V(G_2)$, where $I(G_1)$ is the set of inserted vertices of $mathcal{S}(G_1)$. In this paper we determine the adjacency spectra, the Laplacian spectra and the signless Laplacian spectra of $G_1dot{vee}G_2$ (respectively, $G_1underline{vee}G_2$) for a regular graph $G_1$ and an arbitrary graph $G_2$, in terms of the corresponding spectra of $G_1$ and $G_2$. As applications, these results enable us to construct infinitely many pairs of cospectral graphs. We also give the number of the spanning trees and the Kirchhoff index of $G_1dot{vee}G_2$ (respectively, $G_1underline{vee}G_2$) for a regular graph $G_1$ and an arbitrary graph $G_2$.



قيم البحث

اقرأ أيضاً

108 - Pengli Lu , Yufang Miao 2013
The subdivision graph $mathcal{S}(G)$ of a graph $G$ is the graph obtained by inserting a new vertex into every edge of $G$. Let $G_1$ and $G_2$ be two vertex disjoint graphs. The emph{subdivision-vertex corona} of $G_1$ and $G_2$, denoted by $G_1odo t G_2$, is the graph obtained from $mathcal{S}(G_1)$ and $|V(G_1)|$ copies of $G_2$, all vertex-disjoint, by joining the $i$th vertex of $V(G_1)$ to every vertex in the $i$th copy of $G_2$. The emph{subdivision-edge corona} of $G_1$ and $G_2$, denoted by $G_1circleddash G_2$, is the graph obtained from $mathcal{S}(G_1)$ and $|I(G_1)|$ copies of $G_2$, all vertex-disjoint, by joining the $i$th vertex of $I(G_1)$ to every vertex in the $i$th copy of $G_2$, where $I(G_1)$ is the set of inserted vertices of $mathcal{S}(G_1)$. In this paper we determine the adjacency spectra, the Laplacian spectra and the signless Laplacian spectra of $G_1odot G_2$ (respectively, $G_1circleddash G_2$) in terms of the corresponding spectra of $G_1$ and $G_2$. As applications, the results on the spectra of $G_1odot G_2$ (respectively, $G_1circleddash G_2$) enable us to construct infinitely many pairs of cospectral graphs. The adjacency spectra of $G_1odot G_2$ (respectively, $G_1circleddash G_2$) help us to construct many infinite families of integral graphs. By using the Laplacian spectra, we also obtain the number of spanning trees and Kirchhoff index of $G_1odot G_2$ and $G_1circleddash G_2$, respectively.
Let $G$ be a simple graph and $I(G)$ be its edge ideal. In this article, we study the Castelnuovo-Mumford regularity of symbolic powers of edge ideals of join of graphs. As a consequence, we prove Minhs conjecture for wheel graphs, complete multipart ite graphs, and a subclass of co-chordal graphs. We obtain a class of graphs whose edge ideals have regularity three. By constructing graphs, we prove that the multiplicity of edge ideals of graphs is independent from the depth, dimension, regularity, and degree of $h$-polynomial. Also, we demonstrate that the depth of edge ideals of graphs is independent from the regularity and degree of $h$-polynomial by constructing graphs.
196 - Xiaotong Li , Xianan Jin , Qi Yan 2021
In this paper, using matrix techniques, we compute the Ihara-zeta function and the number of spanning trees of the join of two semi-regular bipartite graphs. Furthermore, we show that the spectrum and the zeta function of the join of two semi-regular bipartite graphs can determine each other.
Given a strictly increasing sequence $mathbf{t}$ with entries from $[n]:={1,ldots,n}$, a parking completion is a sequence $mathbf{c}$ with $|mathbf{t}|+|mathbf{c}|=n$ and $|{tin mathbf{t}mid tle i}|+|{cin mathbf{c}mid cle i}|ge i$ for all $i$ in $[n] $. We can think of $mathbf{t}$ as a list of spots already taken in a street with $n$ parking spots and $mathbf{c}$ as a list of parking preferences where the $i$-th car attempts to park in the $c_i$-th spot and if not available then proceeds up the street to find the next available spot, if any. A parking completion corresponds to a set of preferences $mathbf{c}$ where all cars park. We relate parking completions to enumerating restricted lattice paths and give formulas for both the ordered and unordered variations of the problem by use of a pair of operations termed textbf{Join} and textbf{Split}. Our results give a new volume formula for most Pitman-Stanley polytopes, and enumerate the signature parking functions of Ceballos and Gonzalez DLeon.
Normaliz is an open-source software for the computation of lattice points in rational polyhedra, or, in a different language, the solutions of linear diophantine systems. The two main computational goals are (i) finding a system of generators of the set of lattice points and (ii) counting elements degree-wise in a generating function, the Hilbert Series. In the homogeneous case, in which the polyhedron is a cone, the set of generators is the Hilbert basis of the intersection of the cone and the lattice, an affine monoid. We will present some improvements to the Normaliz algorithm by subdividing simplicial cones with huge volumes. In the first approach the subdivision points are found by integer programming techniques. For this purpose we interface to the integer programming solver SCIP to our software. In the second approach we try to find good subdivision points in an approximating overcone that is faster to compute.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا