2017
4
1
0
0
Small graphs with exactly two nonnegative eigenvalues
2
2
Let $G$ be a graph with eigenvalues $lambda_1(G)geqcdotsgeqlambda_n(G)$. In this paper we find all simple graphs $G$ such that $G$ has at most twelve vertices and $G$ has exactly two nonnegative eigenvalues. In other words we find all graphs $G$ on $n$ vertices such that $nleq12$ and $lambda_1(G)geq0$, $lambda_2(G)geq0$ and $lambda_3(G)<0$. We obtain that there are exactly $1575$ connected graphs $G$ on $nleq12$ vertices with $lambda_1(G)>0$, $lambda_2(G)>0$ and $lambda_3(G)<0$. We find that among these $1575$ graphs there are just two integral graphs.
1

1
18


Tajedin
Derikvand
Department of Mathematics, Marvdasht Branch, Islamic Azad University, Marvdasht, Iran
Department of Mathematics, Marvdasht Branch,
Iran


Mohammad Reza
Oboudi
Department of Mathematics, College of Sciences, Shiraz University, Shiraz, 7145744776, Iran
Department of Mathematics, College of Sciences,
Iran
mr_oboudi@yahoo.com
Spectrum of graphs
Eigenvalues of graphs
Graphs with exactly two nonnegative eigenvalues
[[1] M.R. Oboudi, Bipartite graphs with at most six nonzero eigenvalues, Ars Mathematica Contemporanea 11 (2016) 315–325.##[2] M.R. Oboudi, Characterization of graphs with exactly two nonnegative eigenvalues, Ars Mathematica Contemporanea 12 (2017) 271–286.##[3] M.R. Oboudi, On the third largest eigenvalue of graphs, Linear Algebra and its Applications 503 (2016) 164–179##[4] M. Petrovi´c, Graphs with a small number of nonnegative eienvalues, Graphs and Combinatorics 15 (1999) 221–232.##[5] J. H. Smith, Symmetry and multiple eigenvalues of graphs, Glas. Mat., Ser. III 12 (1977) No. 1, 38.##]
The Main Eigenvalues of the Undirected Power Graph of a Group
2
2
The undirected power graph of a finite group $G$, $P(G)$, is a graph with the group elements of $G$ as vertices and two vertices are adjacent if and only if one of them is a power of the other. Let $A$ be an adjacency matrix of $P(G)$. An eigenvalue $lambda$ of $A$ is a main eigenvalue if the eigenspace $epsilon(lambda)$ has an eigenvector $X$ such that $X^{t}jjneq 0$, where $jj$ is the allone vector. In this paper we want to focus on the power graph of the finite cyclic group $mathbb{Z}_{n}$ and find a condition on n where $P(mathbb{Z}_{n})$ has exactly one main eigenvalue. Then we calculate the number of main eigenvalues of $P(mathbb{Z}_{n})$ where $n$ has a unique prime decomposition $n = p^{r} p_2$. We also formulate a conjecture on the number of the main eigenvalues of $P(mathbb{Z}_{n})$ for an arbitrary positive integer $n$.
1

19
32


Mehrnoosh
Javarsineh
Department of Pure Mathematics, Faculty of Mathematical Sciences, University of Kashan, Kashan 8731753153, Iran.
Department of Pure Mathematics, Faculty of
Iran
mehrnooshjavar@gmail.com


Gholam Hossein
FathTabar
Department of Pure Mathematics, Faculty of Mathematical Sciences, University of Kashan, Kashan 8731753153, Iran.
Department of Pure Mathematics, Faculty of
Iran
gh.fathtabar@gmail.com
Power graph
Main eigenvalue
Cyclic group
Prime divisor
[[1] P.J. Cameron and Sh. Ghosh, The power graph of a finite group, Discrete Math., Vol. 311 Issue 13 (2011),##pp. 1220–1222.##[2] I. Chakrabarty, Sh. Ghosh and M. K. Sen, Undirected power graphs of semigroups, Semigroup Forum, Vol.##78 Issue 3 (2009), pp. 410–426.##[3] D. Cvetkovi´ c, The main part of the spectrum, divisors and switching of graphs, Publ. Inst. Math. (Beograd) (N.S.), Vol. 37 (1978), pp. 31–38.##[4] D. Cvetkovi´ c, P. Rowlinson and S. Simi´ c, Eigenspaces of graphs, Encyclopedia of Mathematics and its##Applications, 66. Cambridge University Press, Cambridge, (1997).##[5] E. Hagos, Some results on graph spectra, Linear Algebra Appl., Vol 356 (2002), pp. 103–111.##[6] V. Nikiforov, Walks and the spectral radius of graphs, Linear Algebra Appl., Vol. 418 Issue 1 (2006), pp.##257–268.##[7] G. R. Pourgholi, H. YousefiAzari and A. R. Ashrafi, The undirected power graph of a finite group, Bull.##Malays. Math. Sci. Soc., Vol.38 Issue 4 (2015), pp. 1517–1525.##[8] P. Rowlinson, The main eigenvalues of a graph: a survey, Appl. Anal. Discrete Math., Vol. 1 No. 2 (2007),##pp. 445–471.##[9] Y. Teranishi, Main eigenvalues of a graph, Linear and Multilinear Algebra, Vol. 49 Issue 4 (2001), pp.##289–303.##]
On the EdgeDifference and EdgeSum Chromatic Sum of the Simple Graphs
2
2
For a coloring $c$ of a graph $G$, the edgedifference coloring sum and edgesum coloring sum with respect to the coloring $c$ are respectively $sum_c D(G)=sum c(a)c(b)$ and $sum_s S(G)=sum (c(a)+c(b))$, where the summations are taken over all edges $abin E(G)$.
The edgedifference chromatic sum, denoted by $sum D(G)$, and the edgesum chromatic sum, denoted by $sum S(G)$, are respectively the minimum possible values of $sum_c D(G)$ and $sum_c S(G)$, where the minimums are taken over all proper coloring of $c$.
In this work, we study the edgedifference chromatic sum and the edgesum chromatic sum of graphs. In this regard,
we present some necessary conditions for the existence of homomorphism between two graphs. Moreover, some upper and lower bounds for these parameters in terms of the fractional chromatic number are introduced
as well.
1

33
42


S.
Rahimi Sharbaf
School of Mathematical Science, Shahrood University of Technology, Shahrood, Iran.
School of Mathematical Science, Shahrood
Iran


Kh.
Erfani
School of Mathematical Science, Shahrood University of Technology, Shahrood, Iran.
School of Mathematical Science, Shahrood
Iran
edgedifference chromatic sum
edgesum chromatic sum
graph homomorphism
Kneser graph
fractional chromatic number
[[1] M. Alishahi and A. Taherkhani, A Note on Chromatic Sum, To appear, Ars Combinatoria. Available at##arXiv:0802.1936.##[2] E. Kubicka, The chromatic sum of a graph, Western Michigan University, 1989, Michigan.##[3] K. J. Supowit, Finding a Maximum Planar Subset of a Set of Nets in a Channel, Trans. Comp.Aided Des.##Integ. Cir. Sys., 6 (1) (2006) 9394.##[4] M.R. Garey, and D.S. Johnson, Computers and Intractability; A Guide to the Theory of NPCompleteness,##W. H. Freeman & Co., New York, NY, USA, 1990.##[5] K. E. Stecke, Design, planning, scheduling, and control problems of flexible manufacturing systems, Annals##of Operations Research, 3 (1) (1985), 112.##[6] C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice##Hall, Inc., Upper Saddle River, NJ, USA, 1982.##[7] E. K. Burke and B. McCollum and A. Meisels and S. Petrovic and R. Qu, A graphbased hyper heuristic##for educational timetabling problems, European Journal of Operational Research, 176 (1) (2007), 177  192.##[8] D.H. Smith and S. Hurley and S.U. Thiel, Improving heuristics for the frequency assignment problem,##European Journal of Operational Research, 107, (1) (1998)7686.##[9] D. de Werra and Ch. Eisenbeis and S. Lelait and B. Marmol, On a graph theoretical model for cyclic register##allocation, Discrete Applied Mathematics, 93 (23) (1999) 191203.##[10] M. Gamache and A. Hertz and J. O. Ouellet, A Graph Coloring Model for a Feasibility Problem in Monthly##Crew Scheduling with Preferential Bidding, Comput. Oper. Res., 34 (8) (2007) 23842395.##[11] C. A. Glass, Bag rationalisation for a food manufacturer, Journal of the Operational Research Society, 53##(5) (2002) 544551.##[12] P. Erdos and E. Kubicka and A. J. Schwenk, Graphs that require many colors to achieve their chromatic##sum, In Proceedings of the Twentieth Southeastern Conference on Combinatorics Graph Theory and##Computing, 71 (1990) 1728.##[13] Yu. Li, C. Lucet, A. Moukrim, K. Sghiouer, Greedy Algorithms for the Minimum Sum Coloring Problem,##(2007) Sousse, Tunisia.##[14] H. Hajiabolhassan and M.L. Mehrabadi and R. Tusserkani, Minimal coloring and strength of graphs, Dis##crete Mathematics, 215 (1) (2000) 265  270.##[15] H. Hajiabolhassan and M. L. Mehrabadi and R. Tusserkani, Tabular Graphs and Chromatic Sum, Discrete##Mathematics, 304 (13) (2005) 11–22.##[16] L. G. Kroon, A. Sen, H. Deng and A. Roy, The Optimal Cost Chromatic Partition problem for trees and##interval graphs, GraphTheoretic Concepts in Computer Science: 22nd International Workshop (1997)##[17] T. Jiang and D. B. West, Coloring of Trees with Minimum Sum of Colors, J. Graph Theory, 32 (4) (1999)##354–358.##[18] E. Kubicka A. J. and Schwenk, An Introduction to Chromatic Sums, Proceedings of the 17th Conference##on ACM Annual Computer Science Conference, (1989) 3945.##[19] , C. Thomassen and P. Erdos and Y. Alavi and P. J. Malde and A. J. Schwenk, Tight bounds on the##chromatic sum of a connected graph, Journal of Graph Theory, 13 (3) (1989) 353357.##[20] U. Benlic and J. K. Hao, A Study of Breakout Local Search for the Minimum Sum Coloring Problem,##Simulated Evolution and Learning: 9th International Conference, (2012) 128137.##[21] M. Malafiejski, Sum coloring of graphs, Contemporary Mathematics: Graph Colorings, (2004) 5565.##[22] E..R. Scheinerman and D.H. Ullman, Fractional graph theory: A rational approach to the theory of graphs,##John Wiley & Sons Inc., New York, 1997.##[23] P. Hell and J. Nesatril, Graphs and homomorphisms, Oxford University Press, 2004.##]
On twodimensional Cayley graphs
2
2
A subset W of the vertices of a graph G is a resolving set for G when for each pair of distinct vertices u,v in V (G) there exists w in W such that d(u,w)≠d(v,w). The cardinality of a minimum resolving set for G is the metric dimension of G. This concept has applications in many diverse areas including network discovery, robot navigation, image processing, combinatorial search and optimization. The problem of finding metric dimension is NPcomplete for general graphs but the metric dimension of trees can be obtained using a polynomial time algorithm. In this paper, we investigate the metric dimension of Cayley graphs on dihedral groups and we characterize a family of them.
1

43
50


Ali
Behtoei
Department of Mathematics
Imam Khomeini International University,
P.O, Box 3414916818
Qazvin, Iran
Department of Mathematics
Imam Khomeini Internatio
Iran
a.behtoei@sci.ikiu.ac.ir


yasser
Golkhandy Pour
Department of Mathematics, Faculty of sciences, Imam Khomeini International University, Qazvin, Iran
Department of Mathematics, Faculty of sciences,
Iran
y.golkhandypour@edu.ikiu.ac.ir
Resolving set
Metric dimension
Cayley graph
Dihedral group
[[1] M. Ali, G. Ali, M. Imran, A.Q. Baig, M.K.F. Shaq, On the metric dimension of Mobius ladders, Ars Combin. 105 (2012) 103410. ##[2] Z. Beerliova, F. Eberhard, T. Erlebach, A. Hall, M. Hoffmann, M. Mihalak, L.S. Ram, Network dicovery and verication, IEEE J. Sel. Areas Commun. 24 (2006) 21682181. ##[3] A. Behtoei, A. Davoodi, M. Jannesari, B. Omoomi, A characterization of some graphs with metric dimension two, Discrete Math. Algorithm. Appl. (2017) DOI: 10.1142/S1793830917500276. ##[4] J. Caceres, C. Hernando, M. Mora, I.M. Pelayo, M.L. Puertas, C. Seara, D.R. Wood, On the metric dimension of cartesian products of graphs, SIAM J. Discrete Math. 21 (2007) 423441. ##[5] V. Chvatal, Mastermind, Combinatorica, 3 (1983) 325329 . ##[6] G. Chartrand, L. Eroh, M.A. Johnson, O.R. Ollermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000) 99113. ##[7] F. Harary, R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976) 191195. ##[8] M. Imran, On the metric dimension of barycentric subdivision of Cayley graphs, Acta Math. Appl. Sin. Engl. Ser. 32 (2016) 10671072. ##[9] M. Janessari, B. Omoomi, Characterization of nvertex graphs with metric dimension n3, Math. Bohem. 139 (2014) 123. ##[10] A. Kelenc, D. Kuziak, A. Taranenko, I.G. Yero, Mixed metric dimension of graphs, Appl. Math. Comput. 314 (2017) 429438. ##[11] S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70 (1996) 217229. ##[12] R.A. Melter, I. Tomescu, Metric bases in digital geometry, Comput. Gr. Image Process. 25 (1984) 113121. ##[13] M. Salman, I. Javaid, M.A. Chaudhry, Resolvability in circulant graphs, Acta Math. Sin. (Engl. Ser.) 29 (2012) 18511864. ##[14] A. Sebo, E. Tannier, On metric generators of graphs, Math. Oper. Res. 29 (2004) 383393. ##[15] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549559. ##[16] G. Sudhakara, A.R. Hemanth Kumar, Graphs with metric dimension twoa characterization, World Academy of Science, Engineering and Technology. 36 (2009) 621626.##]
DSpectrum and DEnergy of Complements of Iterated Line Graphs of Regular Graphs
2
2
The Deigenvalues {µ1,…,µp} of a graph G are the eigenvalues of its distance matrix D and form its Dspectrum. The Denergy, ED(G) of G is given by ED (G) =∑i=1p µi. Two non cospectral graphs with respect to D are said to be Dequi energetic if they have the same Denergy. In this paper we show that if G is an rregular graph on p vertices with 2r ≤ p  1, then the complements of iterated line graphs of G are of diameter 2 and that ED(overline{Lk(G)}), k≥2 depends only on p and r. This result leads to the construction of regular Dequi energetic pair of graphs.
1

51
56


Indulal
Gopalapillai
Department of Mathematics, St.Aloysius College, Edathua, Alappuzha
Department of Mathematics, St.Aloysius College,
India
indulalgopal@gmail.com
Distance spectrum
Distance energy
Line graphs
[[1] M. Aouchiche and P. Hansen, Distance spectra of graphs: A survey, Lin. Algebra Appl. 458(2014), 301386. ##[2] B. Bollobas, The diameter of random graphs, Trans. Amer. Math. Soc. 267 (1981), 4152. ##[3] F. Buckley and F. Harary, Distance in Graphs, Addison Wesley, Redwood. 1990. ##[4] F. Buckley, The size of iterated line graphs, Graph Theory Notes New York. 25 (1993), 3336. ##[5] D.M. Cvetkovic, M. Doob and H. Sachs, Spectra of GraphsTheory and Applications, Academic Press, (1980). ##[6] M. Edelberg, M.R. Garey and R.L. Graham, On the distance matrix of a tree, Discrete Math. 14 (1976), 2339. ##[7] F.R. Gantmacher, Applications of the Theory of Matrices (Interscience, New York, 1959), Google Schola. (1969), p.64. ##[8] R.L. Graham and L. Lovasz, Distance matrix polynomials of trees. Adv Math. 29 (1978), 6088. ##[9] I. Gutman, On graphs whose energy exceeds the number of vertices, Lin. Algebra Appl. 429 (1112) (2008), 26702677. ##[10] I. Gutman, S. Zare Firoozabadi, J.A. delaPena and J. Rada, On the energy of regular graphs, Match Commun. Math. Comput. Chem. 57 (2007), 435442. ##[11] W.H. Haemers, Strongly regular graphs with maximal energy, Lin. Algebra Appl. 429 (1112) (2008), 27192723. ##[12] G. Indulal, I. Gutman and A. Vijayakumar, On distance energy of graphs, Match Commun. Math. Comput. Chem. 60 (2008), 461 472. ##[13] G. Indulal and I. Gutman, On the distance spectra of somegraphs, Math. Commun. 13 (2008), 123131. ##[14] G. Indulal and A. Vijayakumar, A note on energy of some graphs, Match Commun. Math. Comput. Chem. 59 (2008), 269274. ##[15] X. Li and J. Zhang, On bicyclic graphs with maximal energy, Lin. Algebra Appl. 427 (2007), 8798. ##[16] J.W. Moon and L. Moser, Almost all (0; 1) matrices are primitive, Studia Sci Math Hungar.1(1966), 153156. ##[17] V. Nikiforov, The energy of graphs and matrices, J. Math. Anal. Appl. 326 (2007), 14721475. ##[18] I. Shparlinski, On the energy of some circulant graphs, Lin. Algebra Appl. 414 (2006), 378382.##]