Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property

A graph is concave-round if its vertices can be circularly enumerated so that the closed neighborhood of each vertex is an interval in the enumeration. In this study, we give a minimal forbidden induced subgraph characterization for the class of concave-round graphs, solving a problem posed by Bang-Jensen, Huang, and Yeo [SIAM J. Discrete Math., 13 (2000), pp. 179–193]. In addition, we show that it is possible to find one such forbidden induced subgraph in linear time in any given graph that is not concave-round. As part of the analysis, we obtain characterizations by minimal forbidden submatrices for the circular-ones property for rows and for the circular-ones property for rows and columns and show that, also for both variants of the property, one of the corresponding forbidden submatrices can be found (if present) in any given matrix in linear time. We make some final remarks regarding connections to some classes of circular-arc graphs.     

There is no (95, 40, 12, 20) strongly regular graph

We show that there is no (95, 40, 12, 20) strongly regular graph and, consequently, there is no (96, 45, 24, 18) strongly regular graph, no nontrivial regular two‐graph on 96 vertices, and no partial geometry pg(4, 9, 2). The main idea of the result is based on the star complement technique and requires a moderate amount of computation.     

Enhanced electronic and nonlinear optical responses of C24N24 cavernous nitride fullerene by decoration with first row transition metals; A computational investigation

The electronic (energy gap and work function) as well as electrical properties (dipole moment, polarizability, and first hyperpolarizabilities) of the first-row transition metals decorated C₂₄N₂₄ cavernous nitride fullerene were explored using DFT calculations. The transition metals are decorated at N4 cavity of C₂₄N₂₄ fullerene. According to our spin polarized computations, the most stable spin state monotonically increases to sextet for Mn@C₂₄N₂₄ and thereafter dropped off gradually to singlet state for Zn@C₂₄N₂₄ system. The findings demonstrate that transition metals can remarkably decrease the HOMO-LUMO energy gap and work function values up to 63% and 21% of bare C₂₄N₂₄, respectively. As can be seen, when the Sc and Ti metals are located above the N4 cavity of fullerene, systems of enhanced static hyperpolarizabilities (β₀) are delivered. These findings might provide an effective strategy to design high performance eletcro-optical materials based on carbon- nitride fullerene.     

Fused-Pentagon Isomers of C60 Fullerene Isolated as Chloro and Trifluoromethyl Derivatives

The carbon cage of buckminsterfullerene I_h-C₆₀, which obeys the Isolated-Pentagon Rule (IPR), can be transformed to non-IPR cages in the course of high-temperature chlorination of C₆₀ or C₆₀Cl₃₀ with SbCl₅. The non-IPR chloro derivatives were isolated chromatographically (HPLC) and characterized crystallographically as ¹⁸⁰⁹C₆₀Cl₁₆, ¹⁸¹⁰C₆₀Cl₂₄, and ¹⁸⁰⁵C₆₀Cl₂₄, which contain, respectively two, four, and four pairs of fused pentagons in the carbon cage. High-temperature trifluoromethylation of the chlorination products with CF₃I afforded a non-IPR CF₃ derivative, ¹⁸⁰⁷C₆₀(CF₃)₁₂, which contains four pairs of fused pentagons in the carbon cage. Addition patterns of non-IPR chloro and CF₃ derivatives were compared and discussed in terms of the formation of stabilizing local substructures on fullerene cages. A detailed scheme of the experimentally confirmed non-IPR C₆₀ isomers obtained by Stone–Wales cage transformations is presented.     

Cayley digraphs and lexicographic product

In this paper, we prove that a Cayley digraph Γ = Cay(G, S) is a nontrivial lexicographical product if and only if there is a nontrivial subgroup H of G such that S∖H is a union of some double cosets of H in G.      

The location of median paths on grid graphs

In this paper we consider the location of a path shaped facility on a grid graph. In the literature this problem was extensively studied on particular classes of graphs as trees or series-parallel graphs. We consider here the problem of finding a path which minimizes the sum of the (shortest) distances from it to the other vertices of the grid, where the path is also subject to an additional constraint that takes the form either of the length of the path or of the cardinality. We study the complexity of these problems and we find two polynomial time algorithms for two special cases, with time complexity of O(n) and O(nℓ) respectively, where n is the number of vertices of the grid and ℓ is the cardinality of the path to be located. The literature about locating dimensional facilities distinguishes between the location of extensive facilities in continuous spaces and network facility location. We will show that the problems presented here have a close connection with continuous dimensional facility problems, so that the procedures provided can also be useful for solving some open problems of dimensional facilities location in the continuous case.     

一类退化椭圆型方程边值问题的适定性

研究一类特殊退化椭圆型方程边值问题的适定性,该类问题与双曲空间中的极小图的Dirichlet问题,曲面的无穷小等距形变刚性问题等等的研究密切相关,而这类方程的特征形式在区域上是变号的,其适定性是值得深入讨论的.最后,得到这类边值问题的H~1弱解的存在性和唯一性.     

A census of semisymmetric cubic graphs on up to 768 vertices

A list is given of all semisymmetric (edge- but not vertex-transitive) connected finite cubic graphs of order up to 768. This list was determined by the authors using Goldschmidt's classification of finite primitive amalgams of index (3,3), and a computer algorithm for finding all normal subgroups of up to a given index in a finitely-presented group. The list includes several previously undiscovered graphs. For each graph in the list, a significant amount of information is provided, including its girth and diameter, the order of its automorphism group, the order and structure of a minimal edge-transitive group of automorphisms, its Goldschmidt type, stabiliser partitions, and other details about its quotients and covers. A summary of all known infinite families of semisymmetric cubic graphs is also given, together with explicit rules for their construction, and members of the list are identified with these. The special case of those graphs having K_1,3 as a normal quotient is investigated in detail. Supported in part by N.Z. Marsden Fund (grant no. UOA 124) and N.Z. Centres of Research Excellence Fund (grant no. UOA 201) Supported in part by “Ministrstvo za šolstvo, znanost in šport Slovenije”, research program no. 101-506. Supported in part by research projects no. Z1-4186-0101 and no. Z1-3124-0101. The fourth author would like to thank the University of Auckland for hospitality during his visit there in 2003.     

Score sets in oriented 3-partite graphs

Let D(U, V, W) be an oriented 3-partite graph with |U|=p, |V|=q and |W|= r. For any vertex x in D(U, V, W), let d x and d-x be the outdegree and indegree of x respectively. Define aui (or simply ai) = q r d ui - d-ui, bvj(or simply bj) = p r d vj - d-vj and Cwk (or simply ck) = p q d wk - d-wk as the scores of ui in U, vj in V and wk in Wrespectively. The set A of distinct scores of the vertices of D(U, V, W) is called its score set. In this paper, we prove that if a1 is a non-negative integer, ai(2≤i≤n - 1) are even positive integers and an is any positive integer, then for n≥3, there exists an oriented 3-partite graph with the score set A = {a1,2∑i=1 ai,…,n∑i=1 ai}, except when A = {0,2,3}. Some more results for score sets in oriented 3-partite graphs are obtained.