eng
University of Isfahan
Transactions on Combinatorics
2251-8657
2251-8665
2017-09-01
6
3
1
9
10.22108/toc.2017.21464
21464
Common extremal graphs for three inequalities involving domination parameters
Vladimir Samodivkin
vl.samodivkin@gmail.com
1
University of Architecture, Civil Engineering and Geodesy (UACEG)
Let $delta (G)$, $Delta (G)$ and $gamma(G)$ be the minimum degree, maximum degree and domination number of a graph $G=(V(G), E(G))$, respectively. A partition of $V(G)$, all of whose classes are dominating sets in $G$, is called a domatic partition of $G$. The maximum number of classes of a domatic partition of $G$ is called the domatic number of $G$, denoted $d(G)$. It is well known that $d(G) leq delta(G) + 1$, $d(G)gamma(G) leq |V(G)|$ cite{ch}, and $|V(G)| leq (Delta(G)+1)gamma(G)$ cite{berge}. In this paper, we investigate the graphs $G$ for which all the above inequalities become simultaneously equalities.
http://toc.ui.ac.ir/article_21464_e634e304e912f76a101c385fa80076eb.pdf
domination/domatic/idomatic number
efficient dominating set
eng
University of Isfahan
Transactions on Combinatorics
2251-8657
2251-8665
2017-09-01
6
3
11
18
10.22108/toc.2017.21463
21463
On the hilbert series of binomial edge ideals of generalized trees
Mahdis Saeedi
mahdis_saeedi@yahoo.com
1
Farhad Rahmati
frahmati@aut.ac.ir
2
Amirkabir University of Technology
Amirkabir University of Technology
In this paper we introduce the concept of generalized trees and compute the Hilbert series of their binomial edge ideals.
http://toc.ui.ac.ir/article_21463_658ac2a187cd8b5573536a652113719e.pdf
binomial edge ideal
hilbert series
short exact sequence
eng
University of Isfahan
Transactions on Combinatorics
2251-8657
2251-8665
2017-09-01
6
3
19
36
10.22108/toc.2017.21466
21466
Binary sequence/array pairs via diference set pairs: A recursive approach
K. T. Arasu
k.arasu@wright.edu
1
Anika Goyal
anikagoyal13@gmail.com
2
Abhishek Puri
puri.abhishek14@gmail.com
3
Wright State University
Dept. of Computer Engg., YMCA University of Science And Technology, Faridabad, HR 121006, India
Dept. of Computer Engg., YMCA University of Science And Technology, Faridabad, HR 121006, India
Binary array pairs with optimal/ideal correlation values and their algebraic counterparts textquotedblleft difference set pairstextquotedblright;(DSPs) in abelian groups are studied. In addition to generalizing known 1-dimensional (sequences) examples, we provide four new recursive constructions, unifying previously obtained ones. Any further advancements in the construction of binary sequences/arrays with optimal/ideal correlation values (equivalently cyclic/abelian difference sets) would give rise to richer classes of DSPs (and hence binary perfect array pairs). Discrete signals arising from DSPs find applications in cryptography, CDMA systems, radar and wireless communications.
http://toc.ui.ac.ir/article_21466_7872b534dc27cd9c3fa2ab7a0cb15ba8.pdf
autocorrelation
binary sequence
perfect sequence pair
difference set pair
eng
University of Isfahan
Transactions on Combinatorics
2251-8657
2251-8665
2017-09-01
6
3
37
43
10.22108/toc.2017.21468
21468
A class of Ramsey-extremal hypergraphs
Brendan D. McKay
brendan.mckay@anu.edu.au
1
Australian National University
In 1991, McKay and Radziszowski proved that, however each $3$-subset of a $13$-set is assigned one of two colours, there is some $4$-subset whose four $3$-subsets have the same colour. More than 25 years later, this remains the only non-trivial classical Ramsey number known for hypergraphs. In this article, we find all the extremal colourings of the $3$-subsets of a 12-set and list some of their properties. We also provide an answer to a question of Dudek, La Fleur, Mubayi and R"odl about the size-Ramsey numbers of hypergraphs.
http://toc.ui.ac.ir/article_21468_114fdfc65b03414f07a821ae0e7d6b38.pdf
hypergraph
Ramsey number
size-Ramsey number
eng
University of Isfahan
Transactions on Combinatorics
2251-8657
2251-8665
2017-09-01
6
3
45
59
10.22108/toc.2017.21473
21473
Distance in cayley graphs on permutation groups generated by $k$ $m$-Cycles
Zohreh Mostaghim
mostaghim@iust.ac.ir
1
Mohammad Hossein Ghaffari
mhghaffari@iust.ac.ir
2
Iran University of Science and Technology
Iran University of Science and Technology
In this paper, we extend upon the results of B. Suceav{u{a}} and R. Stong [Amer. Math. Monthly, 110 (2003) 162--162], which they computed the minimum number of 3-cycles needed to generate an even permutation. Let $Omega^n_{k,m}$ be the set of all permutations of the form $c_1 c_2 cdots c_k$ where $c_i$'s are arbitrary $m$-cycles in $S_n$. Suppose that $Gamma^n_{k,m}$ be the Cayley graph on subgroup of $S_n$ generated by all permutations in $Omega^n_{k,m}$. We find a shortest path joining identity and any vertex of $Gamma^n_{k,m}$, for arbitrary natural number $k$, and $m=2 , , 3,, 4$. Also, we calculate the diameter of these Cayley graphs. As an application, we present an algorithm for finding a short expression of a permutation as products of given permutations.
http://toc.ui.ac.ir/article_21473_2e07c04c5fad360f2c8b9fc03265c648.pdf
Permutation group
Cayley graph
Quadruple cycles
Diameter
Expressions of permutations