Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Magic Distinct Labellings of Simple Graphs
139
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A magic labelling of a graph $G$ with magic sum $s$ is a labelling of the edges of $G$ by nonnegative integers such that for each vertex $vin V$, the sum of labels of all edges incident to $v$ is equal to the same number $s$. Stanley gave remarkable results on magic labellings, but the distinct labelling case is much more complicated. We consider the complete construction of all magic labellings of a given graph $G$. The idea is illustrated in detail by dealing with three regular graphs. We give combinatorial proofs. The structure result was used to enumerate the corresponding magic distinct labellings.
rate research
Read More
We find by applying MacMahons partition analysis that all magic labellings of the cube are of eight types, each generated by six basis elements. A combinatorial proof of this fact is given. The number of magic labellings of the cube is thus reobtained as a polynomial in the magic sum of degree $5$. Then we enumerate magic distinct labellings, the number of which turns out to be a quasi-polynomial of period 720720. We also find the group of symmetry can be used to significantly simplify the computation.
Let $G$ be a finite simple non-complete connected graph on ${1, ldots, n}$ and $kappa(G) geq 1$ its vertex connectivity. Let $f(G)$ denote the number of free vertices of $G$ and $mathrm{diam}(G)$ the diameter of $G$. Being motivated by the computation of the depth of the binomial edge ideal of $G$, the possible sequences $(n, q, f, d)$ of integers for which there is a finite simple non-complete connected graph $G$ on ${1, ldots, n}$ with $q = kappa(G), f = f(G), d = mathrm{diam}(G)$ satisfying $f + d = n + 2 - q$ will be determined. Furthermore, finite simple non-complete connected graphs $G$ on ${1, ldots, n}$ satisfying $f(G) + mathrm{diam}(G) = n + 2 - kappa(G)$ will be classified.
In his survey Beyond graph energy: Norms of graphs and matrices (2016), Nikiforov proposed two problems concerning characterizing the graphs that attain equality in a lower bound and in a upper bound for the energy of a graph, respectively. We show that these graphs have at most two nonzero distinct absolute eigenvalues and investigate the proposed problems organizing our study according to the type of spectrum they can have. In most cases all graphs are characterized. Infinite families of graphs are given otherwise. We also show that all graphs satifying the properties required in the problems are integral, except for complete bipartite graphs $K_{p,q}$ and disconnected graphs with a connected component $K_{p,q}$, where $pq$ is not a perfect square.
Hefetz, M{u}tze, and Schwartz conjectured that every connected undirected graph admits an antimagic orientation. In this paper we support the analogous question for distance magic labeling. Let $Gamma$ be an Abelian group of order $n$. A textit{directed $Gamma$-distance magic labeling} of an oriented graph $vec{G} = (V,A)$ of order $n$ is a bijection $vec{l}:V rightarrow Gamma$ with the property that there is a textit{magic constant} $mu in Gamma$ such that for every $x in V(G)$ $ w(x) = sum_{y in N^{+}(x)}vec{l}(y) - sum_{y in N^{-}(x)} vec{l}(y) = mu. $ In this paper we provide an infinite family of odd regular graphs possessing an orientable $mathbb{Z}_{n}$-distance magic labeling. Our results refer to lexicographic product of graphs. We also present a family of odd regular graphs that are not orientable $mathbb{Z}_{n}$-distance magic.
In 2011, Fang et al. in (J. Combin. Theory A 118 (2011) 1039-1051) posed the following problem: Classify non-normal locally primitive Cayley graphs of finite simple groups of valency $d$, where either $dleq 20$ or $d$ is a prime number. The only case for which the complete solution of this problem is known is of $d=3$. Except this, a lot of efforts have been made to attack this problem by considering the following problem: Characterize finite nonabelian simple groups which admit non-normal locally primitive Cayley graphs of certain valency $dgeq4$. Even for this problem, it was only solved for the cases when either $dleq 5$ or $d=7$ and the vertex stabilizer is solvable. In this paper, we make crucial progress towards the above problems by completely solving the second problem for the case when $dgeq 11$ is a prime and the vertex stabilizer is solvable.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
