Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGraphs admitting only constant splines
71
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study {em generalized graph splines,} introduced by Gilbert, Viel, and the last author. For a large class of rings, we characterize the graphs that only admit constant splines. To do this, we prove that if a graph has a particular type of cutset (e.g., a bridge), then the space of splines naturally decomposes as a certain direct sum of submodules. As an application, we use these results to describe splines on a triangulation studied by Zhou and Lai, but over a different ring than they used.
rate research
Read More
A generalized spline on a graph $G$ with edges labeled by ideals in a ring $R$ consists of a vertex-labeling by elements of $R$ so that the labels on adjacent vertices $u, v$ differ by an element of the ideal associated to the edge $uv$. We study the $R$-module of generalized splines and produce minimum generating sets for several families of graphs and edge-labelings: $1)$ for all graphs when the edge-labelings consist of at most two finitely-generated ideals, and $2)$ for cycles when the edge-labelings consist of principal ideals generated by elements of the form $(ax+by)^2$ in the polynomial ring $mathbb{C}[x,y]$. We obtain the generators using a constructive algorithm that is suitable for computer implementation and give several applications, including contextualizing several results in classical (analytic) splines.
A graph $Gamma$ is said to be symmetric if its automorphism group $rm Aut(Gamma)$ acts transitively on the arc set of $Gamma$. In this paper, we show that if $Gamma$ is a finite connected heptavalent symmetric graph with solvable stabilizer admitting a vertex-transitive non-abelian simple group $G$ of automorphisms, then either $G$ is normal in $rm Aut(Gamma)$, or $rm Aut(Gamma)$ contains a non-abelian simple normal subgroup $T$ such that $Gleq T$ and $(G,T)$ is explicitly given as one of $11$ possible exception pairs of non-abelian simple groups. Furthermore, if $G$ is regular on the vertex set of $Gamma$ then the exception pair $(G,T)$ is one of $7$ possible pairs, and if $G$ is arc-transitive then the exception pair $(G,T)=(A_{17},A_{18})$ or $(A_{35},A_{36})$.
Given a graph whose edges are labeled by ideals in a ring, a generalized spline is a labeling of each vertex by a ring element so that adjacent vertices differ by an element of the ideal associated to the edge. We study splines over the ring Z/mZ. Previous work considered splines over domains, in which very different phenomena occur. For instance when the ring is the integers, the elements of bases for spline modules are indexed by the vertices of the graph. However we prove that over Z/mZ spline modules can essentially have any rank between 1 and n. Using the classification of finite Z-modules, we begin the work of classifying splines over Z/mZ and produce minimum generating sets for splines on cycles over Z/mZ. We close with many open questions.
Gromov hyperbolicity is an interesting geometric property, and so it is natural to study it in the context of geometric graphs. It measures the tree-likeness of a graph from a metric viewpoint. In particular, we are interested in circular-arc graphs, which is an important class of geometric intersection graphs. In this paper we give sharp bounds for the hyperbolicity constant of (finite and infinite) circular-arc graphs. Moreover, we obtain bounds for the hyperbolicity constant of the complement and line of any circular-arc graph. In order to do that, we obtain new results about regular, chordal and line graphs which are interesting by themselves.
Let $G$ be a finite, undirected $d$-regular graph and $A(G)$ its normalized adjacency matrix, with eigenvalues $1 = lambda_1(A)geq dots ge lambda_n ge -1$. It is a classical fact that $lambda_n = -1$ if and only if $G$ is bipartite. Our main result provides a quantitative separation of $lambda_n$ from $-1$ in the case of Cayley graphs, in terms of their expansion. Denoting $h_{out}$ by the (outer boundary) vertex expansion of $G$, we show that if $G$ is a non-bipartite Cayley graph (constructed using a group and a symmetric generating set of size $d$) then $lambda_n ge -1 + ch_{out}^2/d^2,,$ for $c$ an absolute constant. We exhibit graphs for which this result is tight up to a factor depending on $d$. This improves upon a recent result by Biswas and Saha who showed $lambda_n ge -1 + h_{out}^4/(2^9d^8),.$ We also note that such a result could not be true for general non-bipartite graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
