Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuotients and lifts of symmetric directed graphs
78
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given a directed graph, an equivalence relation on the graph vertex set is said to be balanced if, for every two vertices in the same equivalence class, the number of directed edges from vertices of each equivalence class directed to each of the two vertices is the same. In this paper we describe the quotient and lift graphs of symmetric directed graphs associated with balanced equivalence relations on the associated vertex sets. In particular, we characterize the quotients and lifts which are also symmetric. We end with an application of these results to gradient and Hamiltonian coupled cell systems, in the context of the coupled cell network formalism of Golubitsky, Stewart and Torok(Patterns of synchrony in coupled cell networks with multiple arrows. {SIAM Journal of Applied Dynamical Systems, 4 (1) (2005) 78-100).
rate research
Read More
We consider the Ihara zeta function $zeta(u,X//G)$ and Artin-Ihara $L$-function of the quotient graph of groups $X//G$, where $G$ is a group acting on a finite graph $X$ with trivial edge stabilizers. We determine the relationship between the primes of $X$ and $X//G$ and show that $Xto X//G$ can be naturally viewed as an unramified Galois covering of graphs of groups. We show that the $L$-function of $X//G$ evaluated at the regular representation is equal to $zeta(u,X)$ and that $zeta(u,X//G)$ divides $zeta(u,X)$. We derive two-term and three-term determinant formulas for the zeta and $L$-functions, and compute several examples of $L$-functions of edge-free quotients of the tetrahedron graph $K_4$.
Let $D$ be a strongly connected digraph. The average distance $bar{sigma}(v)$ of a vertex $v$ of $D$ is the arithmetic mean of the distances from $v$ to all other vertices of $D$. The remoteness $rho(D)$ and proximity $pi(D)$ of $D$ are the maximum and the minimum of the average distances of the vertices of $D$, respectively. We obtain sharp upper and lower bounds on $pi(D)$ and $rho(D)$ as a function of the order $n$ of $D$ and describe the extreme digraphs for all the bounds. We also obtain such bounds for strong tournaments. We show that for a strong tournament $T$, we have $pi(T)=rho(T)$ if and only if $T$ is regular. Due to this result, one may conjecture that every strong digraph $D$ with $pi(D)=rho(D)$ is regular. We present an infinite family of non-regular strong digraphs $D$ such that $pi(D)=rho(D).$ We describe such a family for undirected graphs as well.
An intuitive property of a random graph is that its subgraphs should also appear randomly distributed. We consider graphs whose subgraph densities exactly match their expected values. We call graphs with this property for all subgraphs with $k$ vertices to be $k$-symmetric. We discuss some properties and examples of such graphs. We construct 3-symmetric graphs and provide some statistics.
Let $Sz(G),Sz^*(G)$ and $W(G)$ be the Szeged index, revised Szeged index and Wiener index of a graph $G.$ In this paper, the graphs with the fourth, fifth, sixth and seventh largest Wiener indices among all unicyclic graphs of order $ngeqslant 10$ are characterized; as well the graphs with the first, second, third, and fourth largest Wiener indices among all bicyclic graphs are identified. Based on these results, further relation on the quotients between the (revised) Szeged index and the Wiener index are studied. Sharp lower bound on $Sz(G)/W(G)$ is determined for all connected graphs each of which contains at least one non-complete block. As well the connected graph with the second smallest value on $Sz^*(G)/W(G)$ is identified for $G$ containing at least one cycle.
The neighborhood complex of a graph was introduced by Lovasz to provide topological lower bounds on chromatic number, and more general homomorphism complexes of graphs were further studied by Babson and Kozlov. Such `Hom complexes are also related to reconfiguration problems and a notion of discrete homotopy for graphs. Here we initiate the detailed study of Hom complexes for directed graphs, which have applications in the study of graded posets and resolutions of monomial ideals. Our construction can be seen as a special case of the poset structure on the set of multihomomorphisms in more general categories, as introduced by Kozlov, Matsushita, and others. We relate the topological properties of Hom complexes to certain digraph operations including products, adjunctions, and foldings. We introduce a notion of a neighborhood complex for a directed graph and prove that its homotopy type is recovered as a certain Hom complex. We establish a number of results regarding the topology of these complexes, including the dependence on directed bipartite subgraphs, a directed version of the Mycielksi construction, as well as vanishing theorems for higher homology. Inspired by notions of reconfigurations of directed graph colorings we study the connectivity of Hom complexes into tournaments $T_n$. We obtain a complete answer for the case of transitive $T_n$, where we also describe a connection to mixed subdivisions of dilated simplices. Finally we use paths in the internal hom objects of directed graphs to define various notions of homotopy, and discuss connections to the topology of Hom complexes.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
