Bounds on the clique-transversal number of regular graphs

A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G.The clique-transversal number,denoted Tc(G),is the minimum cardinality of a clique- transversal set in G.In this paper we present the bounds on the clique-transversal number for regular graphs and characterize the extremal graphs achieving the lower bound.Also,we give the sharp bounds on the clique-transversal number for claw-free cubic graphs and we characterize the extremal graphs achieving the lower bound.     

Distance–regular graphs having the M-property

We analyse when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is an M-matrix; that is, it has non-positive off-diagonal elements or, equivalently when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is also the combinatorial Laplacian of another network. When this occurs we say that the distance–regular graph has the M-property. We prove that only distance–regular graphs with diameter up to three can have the M-property and we give a characterization of the graphs that satisfy the M-property in terms of their intersection array. Moreover, we exhaustively analyse strongly regular graphs having the M-property and we give some families of distance–regular graphs with diameter three that satisfy the M-property. Roughly speaking, we prove that all distance–regular graphs with diameter one; about half of the strongly regular graphs; only some imprimitive distance–regular graphs with diameter three, and no distance–regular graphs with diameter greater than three, have the M-property. In addition, we conjecture that no primitive distance–regular graph with diameter three has the M-property.     

New upper bounds for the independence numbers of graphs with vertices in {−1, 0, 1} n and their applications to problems of the chromatic numbers of distance graphs

Upper bounds for the independence numbers in the graphs with vertices at {?1, 0, 1} ⁿ are improved. Their applications to problems of the chromatic numbers of distance graphs are studied.     

Implementing Brouwer’s database of strongly regular graphs

Andries Brouwer maintains a public database of existence results for strongly regular graphs on \(n\le 1300\) vertices. We have implemented most of the infinite families of graphs listed there in the open-source software Sagemath (The Sage Developers, http://www.sagemath.org), as well as provided constructions of the “sporadic” cases, to obtain a graph for each set of parameters with known examples. Besides providing a convenient way to verify these existence results from the actual graphs, it also extends the database to higher values of n.     

The Randi? index and the diameter of graphs

The Randi? indexR(G) of a graph G is defined as the sum of over all edges uv of G, where d_u and d_v are the degrees of vertices u and v, respectively. Let D(G) be the diameter of G when G is connected. Aouchiche et al. (2007) [1] conjectured that among all connected graphs G on n vertices the path P_n achieves the minimum values for both R(G)/D(G) and R(G)−D(G). We prove this conjecture completely. In fact, we prove a stronger theorem: If G is a connected graph, then , with equality if and only if G is a path with at least three vertices.     

Cyclic and simultaneous iterative methods to matrix equations of the form A i X B i = F i

This paper deals with a general type of linear matrix equation problem. It presents new iterative algorithms to solve the matrix equations of the form A _i X?B _i = F _i . These algorithms are based on the incremental subgradient and the parallel subgradient methods. The convergence region of these algorithms are larger than other existing iterative algorithms. Finally, some experimental results are presented to show the efficiency of the proposed algorithms.     

Results of the maximum genus of graphs

In this paper,we provide a new class of up-embeddable graphs,and obtain a tight lower bound on the maximum genus of a class of 2-connected pseudographs of diameter 2 and of a class of diameter 4 multi-graphs.This extends a result of Skoviera.     

Two-party graphs and monotonicity properties of the Poincaré mapping

The local differential of a system of nonlinear differential equations with a T-periodic right-hand side is representable as a directed sign interaction graph. Within the class of balanced graphs, where all paths between two fixed vertices have the same signs, it is possible to estimate the sign structure of the differential of the global Poincaré mapping (a shift in time T). In this case all vertices of a strongly connected graph naturally break into two sets (two parties). As appeared, the influence of variables within one party is positive, while that of variables from different parties is negative. Even having simplified the structure of a local two-party graph (by eliminating its edges), one can still exactly describe the sign structure of the differential of the Poincaré mapping. The obtained results are applicable in the mathematical competition theory.     

On the Ramsey-Turán numbers of graphs and hypergraphs

Let t be an integer, f(n) a function, and H a graph. Define the t-Ramsey-Turán number of H, RT _t (n,H, f(n)), to be the maximum number of edges in an n-vertex, H-free graph G with α _t (G) ≤ f(n), where α _t (G) is the maximum number of vertices in a K _t -free induced subgraph of G. Erd?s, Hajnal, Simonovits, Sós and Szemerédi [6] posed several open questions about RT _t (n,K _s , o(n)), among them finding the minimum ? such that RT _t (n,K _t+? , o(n)) = Ω(n ²), where it is easy to see that RT _t (n,K _t+1, o(n)) = o(n ²). In this paper, we answer this question by proving that RT _t (n,K _t+2, o(n)) = Ω(n ²); our constructions also imply several results on the Ramsey-Turán numbers of hypergraphs.     

Turán-type bounds for distance graphs

A lower bound is obtained for the number of edges in a distance graph G in an infinitesimal plane layer ?² × [0, ε] ^d , which relates the number of edges e(G), the number of vertices ν(G), and the independence number α(G). It is proved that \(e\left( G \right) \geqslant \frac{{19\nu \left( G \right) - 50\alpha \left( G \right)}}{3}\). This result generalizes a previous bound for distance graphs in the plane. It substantially improves Turán’s bound in the case where \(\frac{1}{5} \leqslant \frac{{\alpha \left( G \right)}}{{\nu \left( G \right)}} \leqslant \frac{2}{7}\).     

On a conjecture of the Randić index and the minimum degree of graphs

The Randi? index $R\left(G\right)$ of a graph $G$ is defined by $R\left(G\right)={\sum }_{uv}\frac{1}{\sqrt{d\left(u\right)d\left(v\right)}}$, where $d\left(u\right)$ is the degree of a vertex $u$ and the summation extends over all edges $uv$ of $G$. Delorme et al. (2002)  [6] put forward a conjecture concerning the minimum Randi? index among all$n$-vertex connected graphs with the minimum degree at least $k$. In this work, we show that the conjecture is true given the graph contains $k$ vertices of degree $n?1$. Further, it is true among $k$-trees.     

Strongly regular graphs with Hoffman’s condition

It is known that if the minimal eigenvalue of a graph is ?2, then the graph satisfies Hoffman’s condition; i.e., for any generated complete bipartite subgraph K _1,3 with parts {p} and {q ₁, q ₂, q ₃}, any vertex distinct from p and adjacent to two vertices from the second part is not adjacent to the third vertex and is adjacent to p. We prove the converse statement, formulated for strongly regular graphs containing a 3-claw and satisfying the condition gm > 1.     

Amply regular graphs with Hoffman’s condition

It is known that, if the minimal eigenvalue of a graph is ?2, then the graph satisfies Hoffman’s condition: for any generated complete bipartite subgraph K _1,3 (a 3-claw) with parts {p} and {q ₁, q ₂, q ₃}, any vertex distinct from p and adjacent to the vertices q ₁ and q ₂ is adjacent to p but not adjacent to q ₃. We prove the converse statement for amply regular graphs containing a 3-claw and satisfying the condition µ > 1.     

On graphs without crowns with regularμ-subgraphs

Anm-crown is the complete tripartite graphK _{1, 1,m} with parts of order 1, 1,m, and anm-claw is the complete bipartite graphK _1,m with parts of order 1,m, wherem ≥ 3. A vertexa of a graph Γ is calledweakly reduced iff the subgraph {x є Γ ‖a ^⊥ =x ^⊥} consists of one vertex. A graph Γ is calledweakly reduced iff all its vertices are weakly reduced. In the present paper we classify all connected weakly reduced graphs without 3-crowns, all of whose μ-subgraphs are regular graphs of constant nonzero valency. In particular, we generalize the characterization of Grassman and Johnson graphs due to Numata, and the characterization of connected reduced graphs without 3-claws due to Makhnev. Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 874–881, June, 2000. This research was supported by the Russian Foundation for Basic Research under grant No. 99-01-00462.     

Amply regular graphs with Hoffman’s condition

It is known that, if the minimal eigenvalue of a graph is −2, then the graph satisfies Hoffman’s condition: for any generated complete bipartite subgraph K _1,3 (a 3-claw) with parts {p} and {q ₁, q ₂, q ₃}, any vertex distinct from p and adjacent to the vertices q ₁ and q ₂ is adjacent to p but not adjacent to q ₃. We prove the converse statement for amply regular graphs containing a 3-claw and satisfying the condition μ > 1.     

Unmixed bipartite graphs and sublattices of the Boolean lattices

The correspondence between unmixed bipartite graphs and sublattices of the Boolean lattice is discussed. By using this correspondence, we show existence of squarefree quadratic initial ideals of toric ideals arising from minimal vertex covers of unmixed bipartite graphs.     

Skew-symmetric association schemes with two classes and strongly regular graphs of type L 2n−1(4n−1)

A construction of a pair of strongly regular graphs ⁿ and ⁿ of type L _2n–1(4n–1) from a pair of skew-symmetric association schemes W, W of order 4n–1 is presented. Examples of graphs with the same parameters as ⁿ and ⁿ, i.e., of type L _2n–1(4n–1), were known only if 4n–1=p ³, where p is a prime. The first new graph appearing in the series has parameters (v, k, )=(225, 98, 45). A 4-vertex condition for relations of a skew-symmetric association scheme (very similar to one for the strongly regular graphs) is introduced and is proved to hold in any case. This has allowed us to check the 4-vertex condition for ⁿ and ⁿ, thus to prove that ⁿ and ⁿ are not rank three graphs if n>2.