فهرست مطالب

Transactions on Combinatorics - Volume:2 Issue: 2, Jun 2013

Transactions on Combinatorics
Volume:2 Issue: 2, Jun 2013

  • تاریخ انتشار: 1392/03/11
  • تعداد عناوین: 7
|
  • S. Saqaeeyan, Esmaeil Mollaahmadi, Ali Dehghan Pages 1-7
    The colorful paths and rainbow paths have been considered by several authors.A colorful directed path in a digraph $G$ is a directed path with $chi(G)$ vertices whose colors are different. A $v$-colorful directed path is such a directed path, starting from $v$. We prove that for a given $3$-regular triangle-free digraph $G$ determining whether there is a proper $chi(G)$ coloring of $G$ such that for every $v in V (G)$, there exists a $v$-colorful directed path is $ mathbf{NP} $ complete.
    Keywords: Colorful Directed Paths, Computational Complexity, Vertex Coloring
  • Mohammad Gholami, Mehdi Samadieh Pages 9-17
    In this paper, we consider a class of column-weight two quasi-cyclic low-density parity check codes in which the girth can be large enough, as an arbitrary multiple of 8. Then we devotea convolutional form to these codes, such that their generator matrix can be obtained by elementary row and column operations on the parity-check matrix. Finally, we show that the free distance of the convolutional codes is equal to the minimum distance of their block counterparts.
    Keywords: LDPC codes, convolutional codes, girth
  • Hossein Moshtagh, Amir Rahnamai Barghi Pages 19-26
    ‎The Frobenius complement of a given Frobenius group acts on its kernel‎. ‎The scheme which is arisen from the orbitals of this action is called Ferrero pair scheme‎. ‎In this paper‎, ‎we show that the fibers of a Ferrero pair scheme consist of exactly one singleton fiber and every two fibers with more than one point have the same cardinality‎. ‎Moreover‎, ‎it is shown that the restriction of a Ferrero pair scheme on each fiber is isomorphic to a regular scheme‎. ‎Finally‎, ‎we prove that for any prime $p$‎, ‎there exists a Ferrero pair $p$-scheme‎, ‎and if $p> 2$‎, ‎then the Ferrero pair $p$-schemes of the same rank are all isomorphic‎.
    Keywords: ýFrobenius groupý, ýOribtalý, ýScheme
  • Masoud Ariannejad, Mojgan Emami Pages 27-33
    We give a new recursive method to compute the number of cliques and cycles of a graph. This method is related, respectively to the number of disjoint cliques in the complement graph and to the sum of permanent function over all principal minors of the adjacency matrix of the graph. In particular, let $G$ be a graph and let $overline {G}$ be its complement, then given the chromatic polynomial of $overline {G}$, we give a recursive method to compute the number of cliques of $G$. Also given the adjacency matrix $A$ of $G$ we give a recursive method to compute the number of cycles by computing the sum of permanent function of the principal minors of $A$. In both cases we confront to a new computable parameter which is defined as the number of disjoint cliques in $G$.
    Keywords: Graph, Cycle, Clique
  • Ramin Kazemi Pages 35-40
    In this paper we study the Zagreb index in bucket recursive trees containing buckets with variable capacities. This model was introduced by Kazemi in 2012. We obtain the mean and variance of the Zagreb index and introduce a martingale based on this quantity.
    Keywords: Bucket recursive trees with variable capacities of buckets, Zagreb index, martingale
  • Abbas Heydari Pages 41-46
    Let G be a simple connected graph and {v_1,v_2,..., v_k} be the set of pendent (vertices of degree one) vertices of G. The reduced distance matrix of G is an square matrix whose (i,j)-entry is the topological distance between v_i and v_j of G. In this paper, we obtain the spectrum of the reduced distance matrix of regular dendrimers.
    Keywords: Reduced Distance Matrix, Spectrum, Regular Dendrimers
  • N. Paramaguru, R. Sampathkumar Pages 47-72
    A modular $k$-coloring, $kge 2,$ of a graph $G$ without isolated vertices is a coloring of the vertices of $G$ with the elements in $mathbb{Z}_k$ having the property that for every two adjacent vertices of $G,$ the sums of the colors of the neighbors are different in $mathbb{Z}_k.$ The minimum $k$ for which $G$ has a modular $k-$coloring is the modular chromatic number of $G.$ Except for some special cases modular chromatic number of $C_msquare P_n$ is determined.
    Keywords: modular coloring, modular chromatic number, Cartesian product