Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUpper Bounds on the Automorphism Group of a Graph
97
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We give upper bounds on the order of the automorphism group of a simple graph
rate research
Read More
The permanent of a multidimensional matrix is the sum of products of entries over all diagonals. By Mincs conjecture, there exists a reachable upper bound on the permanent of 2-dimensional (0,1)-matrices. In this paper we obtain some generalizations of Mincs conjecture to the multidimensional case. For this purpose we prove and compare several bounds on the permanent of multidimensional (0,1)-matrices. Most estimates can be used for matrices with nonnegative bounded entries.
Graph associahedra are generalized permutohedra arising as special cases of nestohedra and hypergraphic polytopes. The graph associahedron of a graph $G$ encodes the combinatorics of search trees on $G$, defined recursively by a root $r$ together with search trees on each of the connected components of $G-r$. In particular, the skeleton of the graph associahedron is the rotation graph of those search trees. We investigate the diameter of graph associahedra as a function of some graph parameters. It is known that the diameter of the associahedra of paths of length $n$, the classical associahedra, is $2n-6$ for a large enough $n$. We give a tight bound of $Theta(m)$ on the diameter of trivially perfect graph associahedra on $m$ edges. We consider the maximum diameter of associahedra of graphs on $n$ vertices and of given tree-depth, treewidth, or pathwidth, and give lower and upper bounds as a function of these parameters. Finally, we prove that the maximum diameter of associahedra of graphs of pathwidth two is $Theta (nlog n)$.
The Wiener index of a connected graph is the summation of all distances between unordered pairs of vertices of the graph. In this paper, we give an upper bound on the Wiener index of a $k$-connected graph $G$ of order $n$ for integers $n-1>k ge 1$: [W(G) le frac{1}{4} n lfloor frac{n+k-2}{k} rfloor (2n+k-2-klfloor frac{n+k-2}{k} rfloor).] Moreover, we show that this upper bound is sharp when $k ge 2$ is even, and can be obtained by the Wiener index of Harary graph $H_{k,n}$.
The bondage number $b(G)$ of a graph $G$ is the smallest number of edges whose removal from $G$ results in a graph with larger domination number. Let $G$ be embeddable on a surface whose Euler characteristic $chi$ is as large as possible, and assume $chileq0$. Gagarin-Zverovich and Huang have recently found upper bounds of $b(G)$ in terms of the maximum degree $Delta(G)$ and the Euler characteristic $chi(G)=chi$. In this paper we prove a better upper bound $b(G)leqDelta(G)+lfloor trfloor$ where $t$ is the largest real root of the cubic equation $z^3 + z^2 + (3chi - 8)z + 9chi - 12=0$; this upper bound is asymptotically equivalent to $b(G)leqDelta(G)+1+lfloor sqrt{4-3chi} rfloor$. We also establish further improved upper bounds for $b(G)$ when the girth, order, or size of the graph $G$ is large compared with its Euler characteristic $chi$.
A $q$-analogue of a $t$-design is a set $S$ of subspaces (of dimension $k$) of a finite vector space $V$ over a field of order $q$ such that each $t$ subspace is contained in a constant $lambda$ number of elements of $S$. The smallest nontrivial feasible parameters occur when $V$ has dimension $7$, $t=2$, $q=2$, and $k=3$; which is the $q$-analogue of a $2$-$(7,3,1)$ design, the Fano plane. The existence of the binary $q$-analogue of the Fano plane has yet to be resolved, and it was shown by Kiermaier et al. (2016) that such a configuration must have an automorphism group of order at most $2$. We show that the binary $q$-analogue of the Fano plane has a trivial automorphism group.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
