فهرست مطالب

Transactions on Combinatorics
Volume:6 Issue: 2, Jun 2017

  • تاریخ انتشار: 1396/01/18
  • تعداد عناوین: 5
|
  • Farhad Rahmati *, Ali Mahdavi Pages 1-6
    Let f≠1,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ý.
    Keywords: ?Frobenius number?, ?Frobenius vector?, ?Numerical semigroup?, ?simplicial affine semigroup
  • Wai Chee Shiu * Pages 7-17
    Let G=(V,E) be a simple graphý. ýAn edge labeling f:E→{0,1} induces a vertex labeling f:V→\Z2 defined by f(v)≡∑uv∈Ef(uv)(mod2) for each v∈Vý, ýwhere \Z2={0,1} is the additive group of order 2ý. ýFor i∈{0,1}ý, ýletý ýef(i)=|f−1(i)| and vf(i)=|(f)−1(i)|ý. ýA labeling f is called edge-friendly ifý ý|ef(1)−ef(0)|≤1ý. ýIf(G)=vf(1)−vf(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ý.
    Keywords: ?Full edge-friendly index sets?, ?edge-friendly index?, ?edge-friendly labeling?, ?complete bipartite graph
  • Fatemeh Sadat Mousavi *, Massomeh Noori Pages 19-30
    Let G be a graph and χ′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 χ′aa(G□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 χ′aa(Cm□Cn) is at most 6 fo every m≥3 and n≥3ý. ýMoreover in some cases we find the exact value of χ′aa(Cm□Cn)ý.
    Keywords: ?Acyclic edge coloring?, ?adjacent vertex distinguishing acyclic edge coloring?, ?adjacent vertex distinguishing acyclic edge chromatic number
  • Narges Ghareghani * Pages 31-35
    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.
    Keywords: Nowhere zero flow in bidirected graphs, zero-sum flow, Eulerian graphs
  • Charlotte Brennan *, Aubrey Blecher, Arnold Knopfmacher, Toufik Mansour Pages 37-48
    We define [k]={1ý,ý2ý,ý3,…,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ý.
    Keywords: ?words?, ?bargraphs?, ?site-perimeter?, ?generating functions