Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAutomorphisms of the double cover of a circulant graph of valency at most 7
57
0
0.0
(
0
)
Added by
{\\DJ}or{\\dj}e Mitrovi\\'c
Publication date
2021
fields
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A graph $X$ is said to be unstable if the direct product $X times K_2$ (also called the canonical double cover of $X$) has automorphisms that do not come from automorphisms of its factors $X$ and $K_2$. It is nontrivially unstable if it is unstable, connected, and non-bipartite, and no two distinct vertices of X have exactly the same neighbors. We find all of the nontrivially unstable circulant graphs of valency at most $7$. (They come in several infinite families.) We also show that the instability of each of these graphs is explained by theorems of Steve Wilson. This is best possible, because there is a nontrivially unstable circulant graph of valency $8$ that does not satisfy the hypotheses of any of Wilsons four instability theorems for circulant graphs.
rate research
Read More
A graph $X$ is said to be unstable if the direct product $X times K_2$ (also called the canonical double cover of $X$) has automorphisms that do not come from automorphisms of its factors $X$ and $K_2$. It is nontrivially unstable if it is unstable, connected, and nonbipartite, and no two distinct vertices of X have exactly the same neighbors. We find three new conditions that each imply a circulant graph is unstable. (These yield infinite families of nontrivially unstable circulant graphs that were not previously known.) We also find all of the nontrivially unstable circulant graphs of order $2p$, where $p$ is any prime number. Our results imply that there does not exist a nontrivially unstable circulant graph of order $n$ if and only if either $n$ is odd, or $n < 8$, or $n = 2p$, for some prime number $p$ that is congruent to $3$ modulo $4$.
For a graph $G,$ we consider $D subset V(G)$ to be a porous exponential dominating set if $1le sum_{d in D}$ $left( frac{1}{2} right)^{text{dist}(d,v) -1}$ for every $v in V(G),$ where dist$(d,v)$ denotes the length of the smallest $dv$ path. Similarly, $D subset V(G)$ is a non-porous exponential dominating set is $1le sum_{d in D} left( frac{1}{2} right)^{overline{text{dist}}(d,v) -1}$ for every $v in V(G),$ where $overline{text{dist}}(d,v)$ represents the length of the shortest $dv$ path with no internal vertices in $D.$ The porous and non-porous exponential dominating number of $G,$ denoted $gamma_e^*(G)$ and $gamma_e(G),$ are the minimum cardinality of a porous and non-porous exponential dominating set, respectively. The consecutive circulant graph, $C_{n, [ell]},$ is the set of $n$ vertices such that vertex $v$ is adjacent to $v pm i mod n$ for each $i in [ell].$ In this paper we show $gamma_e(C_{n, [ell]}) = gamma_e^*(C_{n, [ell]}) = leftlceil tfrac{n}{3ell +1} rightrceil.$
A graph is said to be a cover graph if it is the underlying graph of the Hasse diagram of a finite partially ordered set. The direct product G X H of graphs G and H is the graph having vertex set V(G) X V(H) and edge set E(G X H) = {(g_i,h_s)(g_j,h_t): g_ig_j belongs to E(G) and h_sh_t belongs to E(H)}. We prove that the direct product M_m(G) X M_n(H) of the generalized Mycielskians of G and H is a cover graph if and only if G or H is bipartite.
The minimum rank of a simple graph $G$ is defined to be the smallest possible rank over all symmetric real matrices whose $ij$th entry (for $i eq j$) is nonzero whenever ${i,j}$ is an edge in $G$ and is zero otherwise. Minimum rank is a difficult parameter to compute. However, there are now a number of known reduction techniques and bounds that can be programmed on a computer; we have developed a program using the open-source mathematics software Sage to implement several techniques. We have also established several additional strategies for computation of minimum rank. These techniques have been used to determine the minimum ranks of all graphs of order 7. This paper contains a list of minimum ranks for all graphs of order at most 7. We also present selected optimal matrices.
For a simple graph $G=(V,E),$ let $mathcal{S}_+(G)$ denote the set of real positive semidefinite matrices $A=(a_{ij})$ such that $a_{ij} eq 0$ if ${i,j}in E$ and $a_{ij}=0$ if ${i,j} otin E$. The maximum positive semidefinite nullity of $G$, denoted $operatorname{M}_+(G),$ is $max{operatorname{null}(A)|Ain mathcal{S}_+(G)}.$ A tree cover of $G$ is a collection of vertex-disjoint simple trees occurring as induced subgraphs of $G$ that cover all the vertices of $G$. The tree cover number of $G$, denoted $T(G)$, is the cardinality of a minimum tree cover. It is known that the tree cover number of a graph and the maximum positive semidefinite nullity of a graph are equal for outerplanar graphs, and it was conjectured in 2011 that $T(G)leq M_+(G)$ for all graphs [Barioli et al., Minimum semidefinite rank of outerplanar graphs and the tree cover number, $ Elec. J. Lin. Alg.,$ 2011]. We show that the conjecture is true for certain graph families. Furthermore, we prove bounds on $T(G)$ to show that if $G$ is a connected outerplanar graph on $ngeq 2$ vertices, then $operatorname{M}_+(G)=T(G)leq leftlceilfrac{n}{2}rightrceil$, and if $G$ is a connected outerplanar graph on $ngeq 6$ vertices with no three or four cycle, then $operatorname{M}_+(G)=T(G)leq frac{n}{3}$. We also characterize connected outerplanar graphs with $operatorname{M}_+(G)=T(G)=leftlceilfrac{n}{2}rightrceil.$
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
