ORIGINAL_ARTICLE
The annihilator graph of a 0-distributive lattice
In this article, for a lattice $\mathcal L$, we define and investigate the annihilator graph $\mathfrak {ag} (\mathcal L)$ of $\mathcal L$ which contains the zero-divisor graph of $\mathcal L$ as a subgraph. Also, for a 0-distributive lattice $\mathcal L$, we study some properties of this graph such as regularity, connectedness, the diameter, the girth and its domination number. Moreover, for a distributive lattice $\mathcal L$ with $Z(\mathcal L)\neq\lbrace 0\rbrace$, we show that $\mathfrak {ag} (\mathcal L) = \Gamma(\mathcal L)$ if and only if $\mathcal L$ has exactly two minimal prime ideals. Among other things, we consider the annihilator graph $\mathfrak {ag} (\mathcal L)$ of the lattice $\mathcal L=(\mathcal D(n),|)$ containing all positive divisors of a non-prime natural number $n$ and we compute some invariants such as the domination number, the clique number and the chromatic number of this graph. Also, for this lattice we investigate some special cases in which $\mathfrak {ag} (\mathcal D(n))$ or $\Gamma(\mathcal D(n))$ are planar, Eulerian or Hamiltonian.
http://toc.ui.ac.ir/article_22285_719ab505eba5ec2cd4bf741957e5ce29.pdf
2018-09-01T11:23:20
2018-09-21T11:23:20
1
18
10.22108/toc.2017.104919.1507
Distributive lattice
Annihilator graph
Zero-divisor graph
Saeid
Bagheri
bagheri_saeid@yahoo.com
true
1
Department of Mathematics, Faculty of Mathematical Sciences, Malayer University, Malayer, Iran
Department of Mathematics, Faculty of Mathematical Sciences, Malayer University, Malayer, Iran
Department of Mathematics, Faculty of Mathematical Sciences, Malayer University, Malayer, Iran
LEAD_AUTHOR
Mahtab
Koohi Kerahroodi
mahtabkh3@gmail.com
true
2
Department of Mathematics, Faculty of Mathematical Sciences, Malayer University, Malayer, Iran.
Department of Mathematics, Faculty of Mathematical Sciences, Malayer University, Malayer, Iran.
Department of Mathematics, Faculty of Mathematical Sciences, Malayer University, Malayer, Iran.
AUTHOR
[1] M. Afkhami, K. Khashyarmanesh and Z. Rajabi, Some results on the annihilator graph of a commutative ring, Czechoslovak Math. Journal, 67 (2017) 151–169.
1
[2] S. Akbari and A. Mohammadian, On zero-divisor graph of finite rings, J. Algebra, 314 (2007) 168–184.
2
[3] M. Alizadeh, A. K. Das, H. R. Maimani, M. R. Pournaki and S. Yassemi, On the diameter and girth of zero-divisor graphs of posets, Discrete Appl. Math., 160 (2012) 1319–1324.
3
[4] D. D. Anderson and M. Naseer, Beck‘s coloring of a commutative ring, J. Algebra, 159 (1993) 500-514.
4
[5] D. F. Anderson and P. Livingston, The zero-divisor graph of a commutative ring, J. Algebra, 217 (1999) 434-447.
5
[6] D. F. Anderson and A. Badawi, The total graph of a commutative ring, J. Algebra, 320 (2008) 2706–2719.
6
[7] D. F. Anderson and S. B. Mulay, On the diameter and girth of a zero-divisor graph, J. Pure Appl. Algebra, 210 (2007) 543–550.
7
[8] A. Badawi, On the annihilator graph of a commutative ring, Comm. Algebra, 42 (2014) 108–121.
8
[9] I. Beck, Coloring of commutative rings, J. Algebra, 116 (1988) 208–226.
9
[10] B. Bollobas and I. Rival, The maximal size of the covering graph of a lattice, Algebra Univ., 9 (1979) 371–373.
10
[11] J. Coykendal, S. Sather-Wagstaff, L. Sheppardson and S. Spiroff, On zero divisor graphs, Progress in commutative Algebra, 2 (2012) 241–299.
11
[12] F. R. Demeyer, T. Mckenzie and K. Schneider, The zero divisor graph of a commutative semigroup, Semigroup Forum, 65 (2002) 206–214.
12
[13] D. Duffus and I. Rival, Path length in the covering graph of a lattice, Discrete Math., 19 (1977) 139–158.
13
[14] S. Dutta and Ch. Lanong, On annihilator graphs of a finite commutative ring, Trans. Comb., 6 no. 1 (2017) 1-11.
14
[15] E. Estaji and K. Khashyarmanesh, The zero divisor graph of a lattice, Results Math., 61 (2012) 1–11.
15
[16] N. D. Filipov, Comparability graphs of partially ordered sets of different types, Colloq. Math. Soc. Janos Bolyai, 33 (1980) 373–380.
16
[17] E. Gedeonova, Lattices whose covering graphs are S-graphs, Colloq. Math. Soc. Janos Bolyai, 33 (1980) 407-435.
17
[18] G. Grätzer, Lattice Theory: Foundation, Birkhauser, Basel, 2011.
18
[19] V. Joshi, Zero divisor graphs of a poset with respect to an ideal, Order, 29 (2012) 499–506.
19
[20] V. Joshi and A. Khiste, On the zero divisor graphs of pm-lattices, Discrete Math., 312 (2012) 2076–2082.
20
[21] V. Joshi and S. Sarode, Diameter and girth of zero divisor graph of multiplicative lattices, Asian-Eur. J. Math., 9 (2016). http://dx.doi.org/10.1142/S1793557116500716.
21
[22] T. G. Lucas, The diameter of a zero divisor graph, J. Algebra, 301 (2006) 174–193.
22
[23] M. J. Nikmehr, R. Nikandish and M. Bakhtyiari, More on the annihilator graph of a commutative ring, Hokkaido Math. J., 46 (2017) 107–118.
23
[24] Y. S. Pawar and N. K. Thakare, pm-lattices, Algebra Univ., 7 (1977) 259–263.
24
[25] T. Tamizh Chelvam and S. Nithya, A note on the zero divisor graph of a lattice, Trans. Comb., 3 no. 3 (2014) 51–59.
25
[26] D. B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall Upper Saddle River, 2001.
26
[27] R. J. Wilson, Introduction to Graph Theory, Fourth edition, Longman, Harlow, 1996.
27
ORIGINAL_ARTICLE
A spectral excess theorem for digraphs with normal Laplacian matrices
The spectral excess theorem, due to Fiol and Garriga in 1997, is an important result, because it gives a good characterization of distance-regularity in graphs. Up to now, some authors have given some variations of this theorem. Motivated by this, we give the corresponding result by using the Laplacian spectrum for digraphs. We also illustrate this Laplacian spectral excess theorem for digraphs with few Laplacian eigenvalues and we show that any strongly connected and regular digraph that has normal Laplacian matrix with three distinct eigenvalues, is distance-regular. Hence such a digraph is strongly regular with girth $g=2$ or $g=3$.
http://toc.ui.ac.ir/article_22346_f0401337d3cc116dc87ace2c1fba2dc5.pdf
2018-09-01T11:23:20
2018-09-21T11:23:20
19
28
10.22108/toc.2018.105873.1513
A Laplacian spectral excess theorem
Distance-regular digraphs
Strongly regular digraphs
Fateme
Shafiei
fatemeh.shafiei66@gmail.com
true
1
Isfahan University of Technology
Isfahan University of Technology
Isfahan University of Technology
LEAD_AUTHOR
[1] J. Bang-Jensen and G. Z. Gregory, Digraphs: Theory, Algorithms and Applications, Springer Monographs in
1
Mathematics, 2nd ed, 2009.
2
[2] A. E. Brouwer, personal homepage: http://www.cwi.nl/~aeb/math/dsrg/dsrg.html.
3
[3] A. E. Brouwer, A. M. Cohen and A. Neumaier, distance-regular Graphs, Springer-Verlag, Berlin-New York,
4
[4] A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Springer, 2012; available online at http://homepages.cwi.nl/~aeb/math/ipm/.
5
[5] F. Comellas, M. A. Fiol, J. Gimbert and M. Mitjana, Weakly distance-regular digraphs, J. Combin. Theory
6
Ser. B, 90 (2004) 233–255.
7
[6] D. M. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs, Theory and Application, VEB Deutscher Verlag
8
der Wissenschaften, Berlin, second edition, 1982.
9
[7] C. Dalfo, E.R. Van Dam, M. A. Fiol and E. Garriga, Dual concepts of almost distance-regularity and the
10
spectral excess theorem, Discrete Math., 312 (2012) 2730–2734.
11
[8] C. Dalfo, E. R. Van Dam, M. A. Fiol, E. Garriga and B. L. Gorissen, On almost distance-regular graphs, J.
12
Combin. Theory Ser. A, 118 (2011) 1094–1113.
13
[9] R. M. Damerell, Distance-transitive and distance-regular digraphs, J. Combin. Theory Ser. B, 31 (1981) 46–53.
14
[10] A. M. Duval, A directed graph version of strongly regular graphs, J. Combin. Theory Ser. A, 47 (1988) 71–100.
15
[11] E. R. Van Dam, The spectral excess theorem for distance-regular graphs: a global (over)view, Electron. J.
16
Combin., 15 (2008), pp. 10.
17
[12] E. R. Van Dam and M. A. Fiol, A short proof of the odd-girth theorem, Electron. J. Combin., 19 (2012) pp.
18
[13] E. R. Van Dam and M. A. Fiol, The Laplacian Spectral Excess Theprem for distance-Regular Graphs, Linear
19
Algebra Appl., 458 (2014) 1–6.
20
[14] Carl D. Meyer, Matrix analysis and applied linear algebra, Philadelphia, USA , 101 (2011) 486–489.
21
[15] M. A. Fiol, Algebraic characterizations of distance-regular graphs, Discrete Math., 246 (2002) 111–129.
22
[16] M. A. Fiol, On some approaches to the spectral excess theorem for nonregular graphs, J. Combin. Theory Ser. A, 120 (2013) 1285–1290.
23
[17] M. A. Fiol and E. Garriga, From local adjacency polynomials to locally pseudo-distance-regular graphs, J.
24
Combin. Theory Ser. B, 71 (1997) 162–183.
25
[18] M. A. Fiol, S. Gago and E. Garriga, A simple proof of the spectral excess theorem for distance-regular graphs, Linear Algebra Appl., 432 (2010) 2418–2422.
26
[19] M. A. Fiol, E. Garriga and J. L. A. Yebra, Locally pseudo-distance-regular graphs, J. Combin.Theory Ser. B,
27
68 (1996) 179–205.
28
[20] G. S. Lee and C. W. Weng, The spectral excess theorem for general graphs, J. Combin. Theory Ser. A, 119 (2012) 1427–1431.
29
[21] G. R. Omidi, A spectral excess theorem for normal digraphs, J. Algebraic Combin., 42 (2015) 537–554.
30
ORIGINAL_ARTICLE
Sufficient conditions for triangle-free graphs to be super-$λ'$
An edge-cut $F$ of a connected graph $G$ is called a restricted edge-cut if $G-F$ contains no isolated vertices. The minimum cardinality of all restricted edge-cuts is called the restricted edge-connectivity $λ'(G)$ of $G$. A graph $G$ is said to be $λ'$-optimal if $λ'(G)=\xi(G)$, where $\xi(G)$ is the minimum edge-degree of $G$. A graph is said to be super-$λ'$ if every minimum restricted edge-cut isolates an edge. In this paper, first, we provide a short proof of a previous theorem about the sufficient condition for $λ'$-optimality in triangle-free graphs, which was given in [J. Yuan and A. Liu, Sufficient conditions for $λ_k$-optimality in triangle-free graphs, Discrete Math., 310 (2010) 981--987]. Second, we generalize a known result about the sufficient condition for triangle-free graphs being super-$λ'$ which was given by Shang et al. in [L. Shang and H. P. Zhang, Sufficient conditions for graphs to be $λ'$-optimal and super-$λ'$, Network}, 309 (2009) 3336--3345].
http://toc.ui.ac.ir/article_22415_297dcf89662c9125339a728e85ad39e3.pdf
2018-09-01T11:23:20
2018-09-21T11:23:20
29
36
10.22108/toc.2018.106623.1523
Triangle-free
restricted edge-cut
super-$ld'$
Huiwen
Cheng
15275013@qq.com
true
1
Department of Mathematics, Zhongguancun Institute
Department of Mathematics, Zhongguancun Institute
Department of Mathematics, Zhongguancun Institute
LEAD_AUTHOR
Yan-Jing
Li
05118322@bjtu.edu.cn
true
2
Department of Mathematics, Beijing Jiaotong University, China
Department of Mathematics, Beijing Jiaotong University, China
Department of Mathematics, Beijing Jiaotong University, China
AUTHOR
ORIGINAL_ARTICLE
$\mathcal{B}$-Partitions, determinant and permanent of graphs
Let $G$ be a graph (directed or undirected) having $k$ number of blocks $B_1, B_2,\hdots,B_k$. A $\mathcal{B}$-partition of $G$ is a partition consists of $k$ vertex-disjoint subgraph $(\hat{B_1},\hat{B_1},\hdots,\hat{B_k})$ such that $\hat{B}_i$ is an induced subgraph of $B_i$ for $i=1,2,\hdots,k.$ The terms $\prod_{i=1}^{k}\det(\hat{B}_i),\ \prod_{i=1}^{k}\text{per}(\hat{B}_i)$ represent the det-summands and the per-summands, respectively, corresponding to the $\mathcal{B}$-partition $(\hat{B_1},\hat{B_1},\hdots,\hat{B_k})$. The determinant (permanent) of a graph having no loops on its cut-vertices is equal to the summation of the det-summands (per-summands), corresponding to all possible $\mathcal{B}$-partitions. In this paper, we calculate the determinant and the permanent of classes of graphs such as block graph, block graph with negatives cliques, signed unicyclic graph, mixed complete graph, negative mixed complete graph, and star mixed block graphs.
http://toc.ui.ac.ir/article_22426_684cba1ff8383118f056e8041a6e743a.pdf
2018-09-01T11:23:20
2018-09-21T11:23:20
37
54
10.22108/toc.2017.105288.1508
$mathcal{B}$-partition
signed graph
mixed block graph
Ranveer
Singh
pg201283008@iitj.ac.in
true
1
Department of Mathematics, Indian Institute of Technology Jodhpur, Jodhpur, India
Department of Mathematics, Indian Institute of Technology Jodhpur, Jodhpur, India
Department of Mathematics, Indian Institute of Technology Jodhpur, Jodhpur, India
LEAD_AUTHOR
Ravindra
Bapat
rbb@isid.ac.in
true
2
Stat-Math Unit, ISI Delhi
Stat-Math Unit, ISI Delhi
Stat-Math Unit, ISI Delhi
AUTHOR
[1] B. D. Acharya, Spectral criterion for cycle balance in networks, J. Graph Theory, 4 (1980) 1–11.
1
[2] R. B. Bapat, Graphs and matrices, 27, Springer, London; Hindustan Book Agency, New Delhi, 2010.
2
[3] R. B. Bapat and S. Roy, On the adjacency matrix of a block graph, Linear and Multilinear Algebra, 62 (2014) 406–418.
3
[4] D. Cartwright and F. Harary, Structural balance: a generalization of Heider’s theory, Psychol Rev., 63 (1956) 277–293.
4
[5] J. Ding and A. Zhou, Eigenvalues of rank-one updated matrices with some applications, Appl. Math. Lett., 20 (2007)
5
1223–1226.
6
[6] D. Easley and J. Kleinberg, Networks, crowds, and markets, 6, Cambridge Univ Press, 2010.
7
[7] F. Harary, On the notion of balance of a signed graph, Michigan Math. J., 2 (1953–54) 143–146.
8
[8] T. Amdeberhan, Determinant of a matrix having diagonal and subdiagonal entries zero, MathOverflow, http://
9
mathoverflow.net/q/264167, (version: 2017-03-10).
10
[9] R. Singh, Determinant of a matrix having diagonal and subdiagonal entries zero, MathOverflow, http://mathoverflow.
11
net/q/264264, (version: 2017-03-10).
12
[10] R. Singh and R. B. Bapat, Eigenvalues of some signed graphs with negative cliques, arXivpreprintarXiv:1702.06322,
13
[11] R. Singh and R. B. Bapat, On characteristic and permanent polynomials of a matrix, Spec. Matrices, 5 (2017) 97–112.
14
[12] H. Zhou, The inverse of the distance matrix of a distance well-defined graph, Linear Algebra Appl., 517 (2017) 11–29.
15
ORIGINAL_ARTICLE
Iota energy of weighted digraphs
The eigenvalues of a digraph are the eigenvalues of its adjacency matrix. The iota energy of a digraph is recently defined as the sum of absolute values of imaginary part of its eigenvalues. In this paper, we extend the concept of iota energy of digraphs to weighted digraphs. We compute the iota energy formulae for the positive and negative weight directed cycles. We also characterize the unicyclic weighted digraphs with cycle weight $ r \in [-1, 1]\backslash \{0\}$ having minimum and maximum iota energy. We obtain well known McClelland upper bound for the iota energy of weighted digraphs. Finally, we find the class of noncospectral equienergetic weighted digraphs.
http://toc.ui.ac.ir/article_22707_8eb3ec61aa18a4a5a2445c45716a4a23.pdf
2018-09-01T11:23:20
2018-09-21T11:23:20
55
73
10.22108/toc.2018.109248.1546
Weighted digraphs
Extremal energy
Equienergetic weighted digraphs
Sumaira
Hafeez
sumaira.hafeez123@gmail.com
true
1
School of Natural Sciences, National university of sciences and Technology Islamabad, Pakistan
School of Natural Sciences, National university of sciences and Technology Islamabad, Pakistan
School of Natural Sciences, National university of sciences and Technology Islamabad, Pakistan
AUTHOR
Mehtab
Khan
mehtabkhan85@gmail.com
true
2
Department of mathematics, school of Natural Sciences, National University of Sciences and Technology Islamabad, Pakistan
Department of mathematics, school of Natural Sciences, National University of Sciences and Technology Islamabad, Pakistan
Department of mathematics, school of Natural Sciences, National University of Sciences and Technology Islamabad, Pakistan
LEAD_AUTHOR