Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNew Examples of Minimal Non-Strongly-Perfect Graphs
96
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A graph is strongly perfect if every induced subgraph H has a stable set that meets every nonempty maximal clique of H. The characterization of strongly perfect graphs by a set of forbidden induced subgraphs is not known. Here we provide several new minimal non-strongly-perfect graphs.
rate research
Read More
A graph is strongly perfect if every induced subgraph H has a stable set that meets every maximal clique of H. A graph is claw-free if no vertex has three pairwise non-adjacent neighbors. The characterization of claw-free graphs that are strongly perfect by a set of forbidden induced subgraphs was conjectured by Ravindra in 1990 and was proved by Wang in 2006. Here we give a shorter proof of this characterization.
Davis and Jedwab (1997) established a great construction theory unifying many previously known constructions of difference sets, relative difference sets and divisible difference sets. They introduced the concept of building blocks, which played an important role in the theory. On the other hand, Polhill (2010) gave a construction of Paley type partial difference sets (conference graphs) based on a special system of building blocks, called a covering extended building set, and proved that there exists a Paley type partial difference set in an abelian group of order $9^iv^4$ for any odd positive integer $v>1$ and any $i=0,1$. His result covers all orders of nonelementary abelian groups in which Paley type partial difference sets exist. In this paper, we give new constructions of strongly regular Cayley graphs on abelian groups by extending the theory of building blocks. The constructions are large generalizations of Polhills construction. In particular, we show that for a positive integer $m$ and elementary abelian groups $G_i$, $i=1,2,ldots,s$, of order $q_i^4$ such that $2m,|,q_i+1$, there exists a decomposition of the complete graph on the abelian group $G=G_1times G_2times cdotstimes G_s$ by strongly regular Cayley graphs with negative Latin square type parameters $(u^2,c(u+1),- u+c^2+3 c,c^2+ c)$, where $u=q_1^2q_2^2cdots q_s^2$ and $c=(u-1)/m$. Such strongly regular decompositions were previously known only when $m=2$ or $G$ is a $p$-group. Moreover, we find one more new infinite family of decompositions of the complete graphs by Latin square type strongly regular Cayley graphs. Thus, we obtain many strongly regular graphs with new parameters.
Inspired by applications of perfect graphs in combinatorial optimization, Chv{a}tal defined t-perfect graphs in 1970s. The long efforts of characterizing t-perfect graphs started immediately, but embarrassingly, even a working conjecture on it is still missing after nearly 50 years. Unlike perfect graphs, t-perfect graphs are not closed under substitution or complementation. A full characterization of t-perfection with respect to substitution has been obtained by Benchetrit in his Ph.D. thesis. Through the present work we attempt to understand t-perfection with respect to complementation. In particular, we show that there are only five pairs of graphs such that both the graphs and their complements are minimally t-imperfect.
We explore graph theoretical properties of minimal prime graphs of finite solvable groups. In finite group theory studying the prime graph of a group has been an important topic for the past almost half century. Recently prime graphs of solvable groups have been characterized in graph theoretical terms only. This now allows the study of these graphs with methods from graph theory only. Minimal prime graphs turn out to be of particular interest, and in this paper we pursue this further by exploring, among other things, diameters, Hamiltonian cycles and the property of being self-complementary for minimal prime graphs. We also study a new, but closely related notion of minimality for prime graphs and look into counting minimal prime graphs.
The Laplacian spread of a graph is the difference between the largest eigenvalue and the second-smallest eigenvalue of the Laplacian matrix of the graph. We find that the class of strongly regular graphs attains the maximum of largest eigenvalues, the minimum of second-smallest eigenvalues of Laplacian matrices and hence the maximum of Laplacian spreads among all simple connected graphs of fixed order, minimum degree, maximum degree, minimum size of common neighbors of two adjacent vertices and minimum size of common neighbors of two nonadjacent vertices. Some other extremal graphs are also provided.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
