ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 11 (2016) 391-395 Nontrivial nuciferous graphs exist Ebrahim Ghorbani Department of Mathematics, K.N. Toosi University of Technology, P. O. Box 16315-1618, Tehran, Iran School ofMathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran Received 3 February 2016, accepted 11 March 2016, published online 22 August 2016 A nuciferous graph is a simple graph with a non-singular 0-1 adjacency matrix A such that all the diagonal entries of A-1 are zero and all the off-diagonal entries of A-1 are nonzero. Sciriha et al. conjectured that except K2, no nuciferous graph exists. We disprove this conjecture. Moreover, we conjecture that there are infinitely many nuciferous Cayley graphs. Keywords: Nuciferous graph, Cayley graph. Math. Subj. Class.: 05C50 1 Introduction Let G be a simple graph with non-singular 0-1 adjacency matrix A. If all the diagonal entries of A-1 are zero and all the off-diagonal entries of A-1 are non-zero, then G is called a nuciferous graph. The concept of nuciferous graphs has arisen in the context of the quantum mechanical theory of the conductivity of non-singular carbon molecules in the Source and Sink Potential model [2]. According to Sciriha [4]: "In the graph-theoretical Source and Sink Potential model, a molecule is either an insulator or a conductor for electrons with energy zero. Of particular interest are two classes of graphs with analogous vertex pairs, i.e., the same behavior for any two- vertex connection. These are uniform-core (insulating for all two-vertex connections) and nuciferous graphs, which conduct for all two-vertex connections. A graph G in the first class reaches the minimum possible nullity when any two distinct connecting vertices are deleted. In the second class, the nullity reaches one, the maximum possible, when any vertex is deleted." E-mail address: e_ghorbani@ipm.ir (Ebrahim Ghorbani) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ Abstract 391 Ars Math. Contemp. 11 (2016) 403-413 To date, the only nuciferous graph known is K2 which we call it the trivial one. In [5] it was conjectured that there are no others. We disprove this conjecture. We remark that in [1] weighted graphs that have an adjacency matrix with the required structure in the inverse as in nuciferous graphs were found. 2 Nuciferous Cayley graphs Making use of the database of vertex-transitive graphs by Gordon Royle [3] and an exhaustive computer search, we found several nuciferous graphs. In fact among vertex-transitive graphs with at most 31 vertices, there are 21 nuciferous graphs. All the 21 nuciferous graphs we found are Cayley graphs: 6 on 24, 3 on 28 and 12 on 30 vertices. Recall that a Cayley graph Cay(T, S) for a given group r and connection set S C r is the graph with vertex set r and with u connected to v if and only if vu-1 e S. Table 1 shows the list of nuciferous Cayley graphs up to 31vertices according to their groups in which Cn and Dn denote cyclic and dihedral groups of order n, respectively, and Symk and Altk denote the symmetric and alternative groups on k elements, respectively. We notice that in Table 1 the Order Group Degree # of nuciferous 24 Di2 x C2 15 1 24 Alt4 x C2 7 2 24 Sym3 x C4 15 1 24 D24 15 1 24 Sym4 7 24 Sym4 15 1 28 D28 13 1 28 D28 15 30 C30 11 1 30 C30 15 1 30 D10 x C3 11 1 30 D10 x C3 22 1 30 De x C5 11 1 30 D30 11 1 30 D30 15 10 Table 1: Number of nuciferous Cayley graphs with at most 31 vertices according to their group two degree 7 graphs on Alt4 x C2 are isomorphic to the two degree 7 graphs on Sym4; all the degree 11 graphs are isomorphic; and the degree 15 graph on C30 is isomorphic to one of the degree 15 graphs on D30. Tables 2 and 3 depict the adjacency matrix A and the inverse A-1 of one of the two nuciferous Cayley graphs with 24 vertices on the group Alt4 x C2. Based on our findings on nuciferous Cayley graphs we pose the following: Conjecture 2.1. There exist infinitely many nuciferous Cayley graphs. 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 0 . Q a* 0 3. a s 1 s a* Table 2: The adjacency matrix of a nuciferous graph with 24 vertices E. Ghorbani: Nontrivial nuciferous graphs exist 395 Acknowledgments I would like to thank Ali Mohammadian for introducing the problem to me, and anonymous referees for their comments which improved the presentation of the paper. I'm also indebted to Patrick Fowler for double-checking the data given in Table 1 and pointing out an error in an earlier version of this paper. The research of the author was in part supported by a grant from IPM (No. 94050114). References [1] A. Farrugia, J. B. Gauci and I. Sciriha, Complete graphs with zero diagonal inverse, Ars Math. Contemp. 11 (2016), 231-245. [2] P. W. Fowler, B. T. Pickup, T. Z. Todorova, R. de los Reyes and I. Sciriha, Omni-conducting fullerenes, Chem. Phys. Lett. 568 (2013), 33-35. [3] G. F. Royle, Combinatorial catalogues, http://staffhome.ecm.uwa.edu.au/ -00013890. [4] I. Sciriha, Molecular graphs with analogous conducting connections, The 4th biennial Canadian Discrete and Algorithmic Mathematics Conference (CanaDAM), Memorial University of Newfoundland (2013). [5] I. Sciriha, M. Debono, M. Borg, P. Fowler and B. T. Pickup, Interlacing-extremal graphs, Ars Math. Contemp. 6 (2013), 261-278.