2013
2
2
2
0
On the complexity of the colorful directed paths in vertex coloring of digraphs
2
2
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 trianglefree 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.
1

1
7


S.
Saqaeeyan
Abadan Branch, Islamic Azad University
Abadan Branch, Islamic Azad University
Iran


Esmaeil
Mollaahmadi
Sharif University of Technology .
Sharif University of Technology .
Iran
mollaahmadi@gmail.com


Ali
Dehghan
Amirkabir University of Technology, Tehran, Iran
Amirkabir University of Technology, Tehran,
Iran
ali_dehghan16@aut.ac.ir
Colorful Directed Paths
Computational Complexity
Vertex Coloring
[S.~Akbari, F.~Khaghanpoor and S.~Moazzeni Colorful paths in vertex coloring of graphs. Preprint. ## S. Akbari, V. Liaghat and A. Nikzad (2011). Colorful paths in vertex coloring of graphs. Electron. J. Combin., Paper 17. 18 (1) , 9## M. Alishahi, A. Taherkhani and C. Thomassen (2011). Rainbow paths with prescribed ends. Electron. J. Combin., Paper 86. 18 (1) , 0## G.~J. Chang, L. D. Tong, J. H. Yan and H. G. Yeh (2002). A note on the GallaiRoyVitaver theorem. Discrete Math.. 256 (12) , 441444## M.~R. Garey and D.~S. Johnson (1979). Computers and intractability: A guide to the theory of $NP$completeness. A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif.. ## H. Li (2001). A generalization of the GallaiRoy theorem. Graphs Combin.. 17 (4) , 681685## C. Lin (2007). Simple proofs of results on paths representing all colors in proper vertexcolorings. Graphs Combin.. 23 (2) , 201203## P.~M. Pardalos and A.~Migdalas (2004). A note on the complexity of longest path problems related to graph
coloring. Appl. Math. Lett.. 17 (1) , 1315## D.~B. West (1996). Introduction to graph theory. Prentice Hall Inc., Upper Saddle River, NJ. ## ]
Convolutional cylindertype blockcirculant cycle codes
2
2
In this paper, we consider a class of columnweight two quasicyclic lowdensity parity check codes in which the girth can be large enough, as an arbitrary multiple of 8. Then we devote a convolutional form to these codes, such that their generator matrix can be obtained by elementary row and column operations on the paritycheck matrix. Finally, we show that the free distance of the convolutional codes is equal to the minimum distance of
their block counterparts.
1

9
17


Mohammad
Gholami
Shahrekord University
Shahrekord University
Iran
gholamimoh@gmail.com


Mehdi
Samadieh
Isfahan Mathematics House
Isfahan Mathematics House
Iran
m.samadieh@mathhouse.org
LDPC codes
convolutional codes
Girth
[R. G. Gallager (1962). Lowdensity paritycheck codes. IRE Trans.. IT8 (1) , 2128## D. J. C. MacKey (1999). Good errorcorrecting codes based on very sparse matrices. IEEE Trans.
Inf. Theory. 45 (2) , 399432## S. Y. Chung, G. D. Forney, T. J. Richardson and R. L. Urbanke (2001). On the design of lowdensity paritycheck codes within 0.0045 dB of the Shannon limit. IEEE Commun. Lett.. 5 (2) , 5860## F. R. Kschischang, B. J. Frey and H. A. Loeliger (2001). Factor graphs and the sumproduct algorithm. IEEE Trans. on Inf. Theory. 47 (2) , 498519## T. D. Souza (2005). Cycle Codes. EPFL / ALGOLMA, SSC 6th semester. ## Y. Levy and D. J. Costello (1993). An algebraic approach to constructing convolutional codes from quasicyclic codes. DIMACS Series in Discr. Math. and Theor. Comp. Sci.. 14, 189198## R. M. Tanner, D. Sridhara, A. Sridharan, T. E. Fuja and D. J. Costello (2004). LDPC block and convolutional codes based on circulant matrices. IEEE Trans. Inform. Theory. 50 (12) , 29662984## R. M. Tanner (1987). Convolutional codes from quasicyclic codes: A link between the theories of block and convolutional codes. Computer Research
Laboratory, Technical Report, USCCRL8721. ## H. Song, J. Liu and B. V. K. V. Kumar (2002). Low complexity LDPC codes for magnetic recording. in IEEE Globecom 2002, Taipei, Taiwan, R.O.C.. ## H. Song, J. Liu and B. V. K. V. Kumar (2002). Low complexity LDPC codes for partial response channels. in IEEE Globecom 2002, Taipei, Taiwan. 2, 12941299## H. Song, J. Liu and B. V. K. V. Kumar (2004). Large girth cycle codes for partial response channels. IEEE Trans. Magn.. 40 part 2 (4) , 30843086## X.Y. Hu and E. Eleftheriou (2004). Binary representation of cycle Tannergraph codes. in Proc. IEEE Intern. Conf. on Commun., Paris, France. , 528532## C. Poulliat, M. Fossorier and D. Declercq (2008). Design of regular $(2, d_c)$ LDPC codes over GF(q) using their binary images. IEEE Trans. Commun.. 56 (10) , 16261635## M. Esmaeili and M. Gholami (2009). Geometricallystructured maximumgirth LDPC block and
convolutional codes. IEEE journal of selected area of commun.. 27 (6) , 831845## M. Esmaeili and M. Gholami (2008). Maximumgirth Slopebased Quasicyclic $(2,kgeq 5)$LDPC Codes. IET Commun.. 2 (10) , 12511262## M. Gholami and M. Esmaeili (2012). Maximumgirth Cylindertype Blockcirculant LDPC Codes. IEEE Trans. on Commun.. 60 (4) , 952962## M. Esmaeili and M. Gholami (2009). TypeIII LDPC Convolutional Codes. Contemporary Engineering Sciences. 2 (2) , 8593## D. J. Costello (1969). A construction technique for randomerror correcting convolutional codes. IEEE Trans. Information Theory. IT15 (5) , 631636## A. J. Viterbi (1967). Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. Information Theory. 12 (2) , 260269## S. Lin and D. J. Costello (2004). Error Control Coding. 2nd Edition, Prentice Hall. ## ]
On schemes originated from Ferrero pairs
2
2
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.
1

19
26


Hossein
Moshtagh
Department of
Mathematics, K. N. Toosi University of Technology,
Department of
Mathematics, K. N. Toosi
Iran
moshtagh@dena.kntu.ac.ir


Amir
Rahnamai Barghi
K. N. Toosi university of Technology University, TehranIran.
K. N. Toosi university of Technology University,
Iran
rahnama@kntu.ac.ir
Frobenius group
Oribtal
Scheme
[K. I. Beidar, W. F. Ke and H. Kiechle (2007). Automorphisms of certain design groups II. J. Algebra. 313 (2) , 672686## R. Brown (2001). Frobenius groups and classical maximal orders. Mem. Amer. Math. Soc.. 151 (717) , 0110## J. D. Dixon and B. Mortimer (1996). Permutation Groups. Graduate Texts in Mathematics, SpringerVerlag, New
York. 163## S. A. Evdokimov and I. N. Ponomarenko (2003). Characterization of cyclotomic schemes and normal Schur rings over a cyclic group. Algebra i Analiz, 14 no. 2 (2002) 1155, translation in St. Petersburg Math. J.. 14 (2) , 189221## S. Evdokimov and I. Ponomarenko (2009). Permutation group approach to association schemes. European J. Combin.. 30, 14561476## B. Huppert (1998). Character theory of finite groups. de Gruyter Expositions in Mathematics, 25 Walter de Gruyter $&$ Co., Berlin. 25## D. S. Passman (1968). Permutation Groups. W. A. Benjamin, Inc., New YorkAmsterdam. ## I. N. Ponomarenko and A. Rahnamai Barghi (2007). On the structure of $p$schemes. (Russian) Zap. Nauchn. Sem. S.Peterburg. Otdel. Mat. Inst. Steklov. (POMI), 344} (2007), translation in J. Math. Sci. (N. Y.). 147 (6) , 72277233## J. A. Wolf (1967). Spaces of Constant Curvature. McGrawHill Book Co., New YorkLondonSydney. ## P. H. Zieschang (2005). Theory of Association Schemes. Springer Monographs in Mathematic, SpringerVerlag, Berlin. ## ]
On the number of cliques and cycles in graphs
2
2
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$.
1

27
33


Masoud
Ariannejad
University of zanjan
University of zanjan
Iran
m.ariannejad@gmail.com


Mojgan
Emami
Department of Mathematics, University of Zanjan
Department of Mathematics, University of
Iran
mojgan.emami@yahoo.com
graph
cycle
Clique
[R. E. L. Aldred and C. Thomassen (1997). Counting cycles in cubic graphs. J. Comb. Theory B. 71, 7984## R. E. L. Aldred and C. Thomassen (2008). On the maximum number of cycles in a planar graph. J. Graph Theory. 57, 255264## N. Alon and S. Frieldland (2008). The maximum number of perfect matchings in graphs with a given degree sequence. Electron. J. Combin., #N13. 15## N. Biggs (1993). Algebraic Graph Theory. Cambridge Mathematical Library, Cambridge University Press, Cambridge. ## F. M. Dong, K. M. Koh and K. L. Teo (2005). Choromatic Polynomials and Choromaticity of Garphs. World Scientific Publication. ## R. C. Entringer and P. J. Slater (1981). On the maximum number of cycles in a graphs. Ars Combin.. 11, 289294## M. Farber, M. Hujter and Z. Tuza (1993). An upper bound on the number of cliques in a graph. Networks. 23 (3) , 207210## J. H. V. Lint and R .M. Wilson (1992). A Course in Combinatorics. Cambridge University Press, Cambridge. ## D. B. West (2001). Introduction to Graph Theory. Prentice Hall, 2nd Ed.. ## D. R. Wood (2007). On the maximum number of cliques in a graph. Graphs Combin.. 23, 337352## ]
Probabilistic analysis of the first Zagreb index
2
2
In this paper we study the first 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 first Zagreb index and introduce a martingale based on this quantity.
1

35
40


Ramin
Kazemi
Department of statistics, Imam Khomeini International University, Qazvin
Department of statistics, Imam Khomeini Internatio
Iran
kazemi@ikiu.ac.ir
Bucket recursive trees with variable capacities of buckets
Zagreb index
martingale
[P. Billingsley (1995). Probability and Measure. A WileyInterscience Publication, John Wiley and Sons, Inc., New York. ## J. Devillersand and A. T. Balaban (1999). Topological indices and
related descriptors in QSAR and QSPR. Gordon and Breach,
Amsterdam. ## I. Gutman and N. Trinajstic (1972). Graph theory and molecular
orbitals. Total $varphi$electron energy of alternant
hydrocarbons. Chem. Phys. Lett.. 17, 535538## M. Kuba and A. Panholzer (2010). A Combinatorial approach to the
analysis of bucket recursive trees. Theoret. Comput. Sci.. 411 (3436) , 32553273## H. Mahmoud and R. Smythe (1995). Probabilistic analysis of bucket
recursive trees. Theoret. Comput. Sci.. 144, 221249## S. Nikolic, I. M. Tolic, N. Trinajstic and I.
Baucc (2000). On the Zagreb indices as complexity
indices. Croatica Chemica Acta.. 73, 909921## S. Nikolic, G. Kovacc, A.
Milicc and N. Trinajstic (2003). On
molecular complexity indices, In Complexity in Chemistry:
Introduction and Fundamentals. eds D. Bonchev and D. H. Rouvray,
Taylor and Francis, London. , 2989## R. Kazemi (2013). Depth in bucket recursive trees with variable
capacities of buckets. Acta Math. Sin. Engl. Ser., DOI: http://dx.doi.org/10.1007/s1011401321152. ## X. Li, Z. Li and L. Wang (2003). The inverse problems for some
topological indices in combinatorial chemistry. J. Comput.
Biol.. 10, 4755## ]
On the spectra of reduced distance matrix of dendrimers
2
2
Let $G$ be a simple connected graph and ${v_1,v_2,ldots, v_k}$ be the set of pendent (vertices of degree one) vertices of $G$. The reduced distance matrix of $G$ is a 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.
1

41
46


Abbas
Heydari
staff
staff
Iran
aheidari@iauarak.ac.ir
Reduced distance matrix
spectrum
Regular Dendrimers
[F. Buckley and F. Harary (1990). Distance in Graphs. AddisonWesley Publishing Company, Advanced Book Program, Redwood City. ## D. H. Rouvray (1986). The role of the topological distance matrix in chemistry. Mathematical and computational concepts in chemistry (Dubrovnik, 1985), Ellis Horwood Ser, Math. Appl., Horwood, Chichester. , 295306## Z. Mihalic, D. Veljan, D. Amic, S. Nikolic, D. Plavsic and N.
Trinajstic (1992). The distance matrix in chemistry. J. Math. Chem.. 11, 223258## E. A. Smolenskii, E. V. Shuvalova, L. K. Maslova, I. V. Chuvaeva and M. S.
Molchanova (2009). Reduced matrix of topological distances with a minimum number of independent parameters: distance vectors and molecular
codes. J. Math. Chem.. 45, 10041020## B. Horvat, T. Pisanski and M. Randic (2008). Terminal polynomials and starlike graphs. MATCH Commun. Math. Comput. Chem.. 60, 493512## M. Randic, J. Zupan and D. VikicTopic (2007). On representation of proteins by starlike
graphs. J. Mol. Graph. Modell.. 26, 290305## M. Randic and J. Zupan (2004). Highly compact 2D graphical representation of DNA sequences. SAR
QSAR Environ. Res. 15, 191205## M. V. Diudea (1995). Wiener Index of Dendrimers. MATCH Commun. Math.Comput. Chem. 32, 7183## M. V. Diudea and B. Parv (1995). Molecular Topology. 25. HyperWiener Index of Dendrimers. J. Chem. Inf. Comput. Sci. 35, 10151018## A. Heydari (2011). Balaban index of regular dendrimers. Optoelectron. Adv. Mater.Rapid Commun.. 5 (11) , 1260162## A. Heydari (2010). Harary index of regular dendrimers. Optoelectron. Adv. Mater.Rapid Commun.. 4 (12) , 22062208## F. Zhang (1999). Matrix Theory, Basic Results and Techniques. Universitext, SpringerVerlag, New York. ## ]
Modular chromatic number of $C_m square P_n$
2
2
A modular $k!$coloring, $kge 2,$ of a graph $G$ 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 their 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.
1

47
72


N.
Paramaguru
Annamalai University
Annamalai University
India


R.
Sampathkumar
Annamalai University
Annamalai University
India
modular coloring
modular chromatic number
Cartesian product
[R. Balakrishnan and K. Ranganathan (2012). A textbook of graph theory. Second Edition, Universitext. Springer, New York. ## F. Okamoto, E. Salehi and P. Zhang (2010). A checkerboard problem and modular colorings of graphs. Bull. Inst. Combin. Appl.. 58, 2947## F. Okamoto, E. Salehi and P. Zhang (2010). A solution to the checkerboard problem. Int. J. Comput. Appl. Math.. 5, 447458## ]