On weighted spectral radius of unraveled balls and normalized Laplacian eigenvalues

For a graph G, the unraveled ball of radius r centered at a vertex v is the ball of radius r centered at v in the universal cover of G. We obtain a lower bound on the weighted spectral radius of unraveled balls of fixed radius in a graph with positive weights on edges, which is used to present an upper bound on the $s^{\text{th}}$ (where $s\ge 2$) smallest normalized Laplacian eigenvalue of irregular graphs under minor assumptions. Moreover, when $s=2$, the result may be regarded as an Alon–Boppana type bound for a class of irregular graphs.     

Connected cubic s-arc-regular Cayley graphs of finite nonabelian simple groups

A graph is said to be s-arc-regular if its full automorphism group acts regularly on the set of its s-arcs. In this paper, we investigate connected cubic s-arc-regular Cayley graphs of finite nonabelian simple groups. Two suffcient and necessary conditions for such graphs to be 1- or 2-arc-regular are given and based on the conditions, several infinite families of 1-or 2-arc-regular cubic Cayley graphs of alternating groups are constructed.     

The number of spanning trees in an (r,s)‐semiregular graph and its line graph

For a graph G, a “spanning tree” in G is a tree that has the same vertex set as G. The number of spanning trees in a graph (network) G, denoted by t(G), is an important invariant of the graph (network) with lots of decisive applications in many disciplines. In the article by Sato (Discrete Math. 2007, 307, 237), the number of spanning trees in an (r, s)‐semiregular graph and its line graph are obtained. In this article, we give short proofs for the formulas without using zeta functions. Furthermore, by applying the formula that enumerates the number of spanning trees in the line graph of an (r, s)‐semiregular graph, we give a new proof of Cayley's Theorem. © 2013 Wiley Periodicals, Inc.     

The reduced expressions in a Coxeter system with a strictly complete Coxeter graph

Let (W,S)$(W,S)$ be a Coxeter system with a strictly complete Coxeter graph. The present paper concerns the set Red(z)$\mathrm{Red}(z)$ of all reduced expressions for any z∈W$z\in W$. By associating each bc-expression to a certain symbol, we describe the set Red(z)$\mathrm{Red}(z)$ and compute its cardinal |Red(z)|$|\mathrm{Red}(z)|$ in terms of symbols. An explicit formula for |Red(z)|$|\mathrm{Red}(z)|$ is deduced, where the Fibonacci numbers play a crucial role.     

Matching energy of unicyclic and bicyclic graphs with a given diameter

Gutman and Wagner proposed the concept of matching energy (ME) and pointed out that the chemical applications of ME go back to the 1970s. Let G be a simple graph of order n and be the roots of its matching polynomial. The ME of G is defined to be the sum of the absolute values of . In this article, we characterize the graphs with minimal ME among all unicyclic and bicyclic graphs with a given diameter d. © 2014 Wiley Periodicals, Inc. Complexity 21: 224–238, 2015     

Optimal Groomings with Grooming Ratios Six and Seven

Grooming uniform all‐to‐all traffic in optical (SONET) rings with grooming ratio C requires the determination of a decomposition of the complete graph into subgraphs each having at most C edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The determination of optimal C‐groomings has been considered for , and completely solved for . For , it has been shown that the lower bound for the drop cost of an optimal C‐grooming can be attained for almost all orders with 5 exceptions and 308 possible exceptions. For , there are infinitely many unsettled orders; especially the case is far from complete. In this paper, we show that the lower bound for the drop cost of a 6‐grooming can be attained for almost all orders by reducing the 308 possible exceptions to 3, and that the lower bound for the drop cost of a 7‐grooming can be attained for almost all orders with seven exceptions and 16 possible exceptions. Moreover, for the unsettled orders, we give upper bounds for the minimum drop costs.     

Formation of lithium,sodium and potassium complexes with 1,3,5‐triamino‐1,3,5‐trideoxy‐cis‐inositol (taci)

Single crystals of (1,3‐diamino‐5‐azaniumyl‐1,3,5‐trideoxy‐cis‐inositol‐κ³O²,O⁴,O⁶)(1,3,5‐triamino‐1,3,5‐trideoxy‐cis‐inositol‐κ³O²,O⁴,O⁶)lithium(I) diiodide dihydrate, [Li(C₆H₁₆N₃O₃)(C₆H₁₅N₃O₃)]I₂·2H₂O or [Li(Htaci)(taci)]I₂·2H₂O (taci is 1,3,5‐triamino‐1,3,5‐trideoxy‐cis‐inositol), (I), bis(1,3,5‐triamino‐1,3,5‐trideoxy‐cis‐inositol‐κ³O²,O⁴,O⁶)sodium(I) iodide, [Na(C₆H₁₅N₃O₃)₂]I or [Na(taci)₂]I, (II), and bis(1,3,5‐triamino‐1,3,5‐trideoxy‐cis‐inositol‐κ³O²,O⁴,O⁶)potassium(I) iodide, [K(C₆H₁₅N₃O₃)₂]I or [K(taci)₂]I, (III), were grown by diffusion of MeOH into aqueous solutions of the complexes. The structures of the Na and K complexes are isotypic. In all three complexes, the taci ligands adopt a chair conformation with axial hydroxy groups, and the metal cations exhibit exclusive O‐atom coordination. The six O atoms of the resulting MO₆ unit define a centrosymmetric trigonal antiprism with approximate D_3d symmetry. The interligand O...O distances increase significantly in the order Li < Na < K. The structure of (I) exhibits a complex three‐dimensional network of R—NH₂—H...NH₂—R, R—O—H...NH₂—R and R—O—H...O(H)—H...NH₂—R hydrogen bonds. The structures of the Na and K complexes consist of a stack of layers, in which each taci ligand is bonded to three neighbours via pairwise O—H...NH₂ interactions between vicinal HO—CH—CH—NH₂ groups.     

Incompatibility networks as models of scale-free small-world graphs

We make a mapping from Sierpinski fractals to a new class of networks, the incompatibility networks, which are scale-free, small-world, disassortative, and maximal planar graphs. Some relevant characteristics of the networks such as degree distribution, clustering coefficient, average path length, and degree correlations are computed analytically and found to be peculiarly rich. The method of network representation can be applied to some real-life systems making it possible to study the complexity of real networked systems within the framework of complex network theory.     

Cycle-maximal triangle-free graphs

We conjecture that the balanced complete bipartite graph _{K⌊n/2⌋,⌈n/2⌉}$K_{\lfloor n/2\rfloor ,\lceil n/2\rceil }$ contains more cycles than any other n$n$-vertex triangle-free graph, and we make some progress toward proving this. We give equivalent conditions for cycle-maximal triangle-free graphs; show bounds on the numbers of cycles in graphs depending on numbers of vertices and edges, girth, and homomorphisms to small fixed graphs; and use the bounds to show that among regular graphs, the conjecture holds. We also consider graphs that are close to being regular, with the minimum and maximum degrees differing by at most a positive integer k$k$. For k=1$k=1$, we show that any such counterexamples have n≤91$n\le 91$ and are not homomorphic to _C5$C_5$; and for any fixed k$k$ there exists a finite upper bound on the number of vertices in a counterexample. Finally, we describe an algorithm for efficiently computing the matrix permanent (a #P$\#P$-complete problem in general) in a special case used by our bounds.     

Perfect 1‐Factorizations of a Family of Cayley Graphs

A 1‐factorization of a graph G is a decomposition of G into edge‐disjoint 1‐factors (perfect matchings), and a perfect 1‐factorization is a 1‐factorization in which the union of any two of the 1‐factors is a Hamilton cycle. We consider the problem of the existence of perfect 1‐factorizations of even order 4‐regular Cayley graphs, with a particular interest in circulant graphs. In this paper, we study a new family of graphs, denoted , which are Cayley graphs if and only if k is even or . By solving the perfect 1‐factorization problem for a large class of graphs, we obtain a new class of 4‐regular bipartite circulant graphs that do not have a perfect 1‐factorization, answering a problem posed in 7 . With further study of graphs, we prove the nonexistence of P1Fs in a class of 4‐regular non‐bipartite circulant graphs, which is further support for a conjecture made in 7 .