On numerical semigroups with embedding dimension three
Ali
Mahdavi
Amirkabir University of Technology
author
Farhad
Rahmati
Amirkabir University of Technology
author
text
article
2017
eng
Let $f\neq1,3$ be a positive integer. We prove that there exists a numerical semigroup $S$ with embedding dimension three such that $f$ is the Frobenius number of $S$. We also show that the same fact holds for affine semigroups in higher dimensional monoids.
Transactions on Combinatorics
University of Isfahan
2251-8657
6
v.
2
no.
2017
1
6
http://toc.ui.ac.ir/article_20736_f17d7b141a073f2b8afd89a9f3d6327d.pdf
dx.doi.org/10.22108/toc.2017.20736
Full edge-friendly index sets of complete bipartite graphs
Wai Chee
Shiu
Hong Kong Baptist University
author
text
article
2017
eng
Let $G=(V,E)$ be a simple graph. An edge labeling $f:E\to \{0,1\}$ induces a vertex labeling $f^+:V\to\Z_2$ defined by $f^+(v)\equiv \sum\limits_{uv\in E} f(uv)\pmod{2}$ for each $v \in V$, where $\Z_2=\{0,1\}$ is the additive group of order 2. For $i\in\{0,1\}$, let $e_f(i)=|f^{-1}(i)|$ and $v_f(i)=|(f^+)^{-1}(i)|$. A labeling $f$ is called edge-friendly if $|e_f(1)-e_f(0)|\le 1$. $I_f(G)=v_f(1)-v_f(0)$ is called the edge-friendly index of $G$ under an edge-friendly labeling $f$. The full edge-friendly index set of a graph $G$ is the set of all possible edge-friendly indices of $G$. Full edge-friendly index sets of complete bipartite graphs will be determined.
Transactions on Combinatorics
University of Isfahan
2251-8657
6
v.
2
no.
2017
7
17
http://toc.ui.ac.ir/article_20739_045d1f054d5254d803c8df777bac0d71.pdf
dx.doi.org/10.22108/toc.2017.20739
Adjacent vertex distinguishing acyclic edge coloring of the Cartesian product of graphs
Fatemeh Sadat
Mousavi
University of Zanjan
author
Massomeh
Noori
University of Zanjan
author
text
article
2017
eng
Let $G$ be a graph and $\chi^{\prime}_{aa}(G)$ denotes the minimum number of colors required for an acyclic edge coloring of $G$ in which no two adjacent vertices are incident to edges colored with the same set of colors. We prove a general bound for $\chi^{\prime}_{aa}(G\square H)$ for any two graphs $G$ and $H$. We also determine exact value of this parameter for the Cartesian product of two paths, Cartesian product of a path and a cycle, Cartesian product of two trees, hypercubes. We show that $\chi^{\prime}_{aa}(C_m\square C_n)$ is at most $6$ fo every $m\geq 3$ and $n\geq 3$. Moreover in some cases we find the exact value of $\chi^{\prime}_{aa}(C_m\square C_n)$.
Transactions on Combinatorics
University of Isfahan
2251-8657
6
v.
2
no.
2017
19
30
http://toc.ui.ac.ir/article_20988_dc6050dc4f36dd95fd12e657ff895814.pdf
dx.doi.org/10.22108/toc.2017.20988
A new proof of validity of Bouchet's conjecture on Eulerian bidirected graphs
Narges
Ghareghani
University of Tehran
author
text
article
2017
eng
Recently, E. M\'{a}\v{c}ajov\'{a} and M. \v{S}koviera proved that every bidirected Eulerian graph which admits a nowhere zero flow, admits a nowhere zero $4$-flow. This result shows the validity of Bouchet's nowhere zero conjecture for Eulerian bidirected graphs. In this paper we prove the same theorem in a different terminology and with a short and simple proof. More precisely, we prove that every Eulerian undirected graph which admits a zero-sum flow, admits a zero-sum $4$-flow. As a conclusion we obtain a shorter proof for the previously mentioned result of M\'{a}\v{c}ajov\'{a} and \v{S}koviera.
Transactions on Combinatorics
University of Isfahan
2251-8657
6
v.
2
no.
2017
31
35
http://toc.ui.ac.ir/article_21362_d500cc0139aaa06f9bbb49637cdb9ec2.pdf
dx.doi.org/10.22108/toc.2017.21362
The site-perimeter of words
Aubrey
Blecher
University of the Witwatersrand
author
Charlotte
Brennan
1 Jan Smuts Avenue
author
Arnold
Knopfmacher
University of the Witwatersrand
author
Toufik
Mansour
University of the Witwatersrand
author
text
article
2017
eng
We define $[k]=\{1, 2, 3,\ldots,k\}$ to be a (totally ordered) {\em alphabet} on $k$ letters. A {\em word} $w$ of length $n$ on the alphabet $[k]$ is an element of $[k]^n$. A word can be represented by a bargraph which is a family of column-convex polyominoes whose lower edge lies on the $x$-axis and in which the height of the $i$-th column in the bargraph equals the size of the $i$-th part of the word. Thus these bargraphs have heights which are less than or equal to $k$. We consider the site-perimeter, which is the number of nearest-neighbour cells outside the boundary of the polyomino. The generating function that counts the site-perimeter of words is obtained explicitly. From a functional equation we find the average site-perimeter of words of length $n$ over the alphabet $[k]$. We also show how these statistics may be obtained using a direct counting method and obtain the minimum and maximum values of the site-perimeters.
Transactions on Combinatorics
University of Isfahan
2251-8657
6
v.
2
no.
2017
37
48
http://toc.ui.ac.ir/article_21465_6b2d0d7534fbdaeab5e1760bad7055c7.pdf
dx.doi.org/10.22108/toc.2017.21465