Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userVertex types in threshold and chain graphs
93
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A graph is called a chain graph if it is bipartite and the neighborhoods of the vertices in each color class form a chain with respect to inclusion. A threshold graph can be obtained from a chain graph by making adjacent all pairs of vertices in one color class. Given a graph $G$, let $lambda$ be an eigenvalue (of the adjacency matrix) of $G$ with multiplicity $k geq 1$. A vertex $v$ of $G$ is a downer, or neutral, or Parter depending whether the multiplicity of $lambda$ in $G-v$ is $k-1$, or $k$, or $k+1$, respectively. We consider vertex types in the above sense in threshold and chain graphs. In particular, we show that chain graphs can have neutral vertices, disproving a conjecture by Alazemi {em et al.}
rate research
Read More
A vertex coloring of a graph $G$ is called distinguishing if no non-identity automorphisms of $G$ can preserve it. The distinguishing number of $G$, denoted by $D(G)$, is the minimum number of colors required for such coloring. The distinguishing threshold of $G$, denoted by $theta(G)$, is the minimum number $k$ such that every $k$-coloring of $G$ is distinguishing. In this paper, we study $theta(G)$, find its relation to the cycle structure of the automorphism group of $G$ and prove that $theta(G)=2$ if and only if $G$ is isomorphic to $K_2$ or $overline{K_2}$. Moreover, we study graphs that have the distinguishing threshold equal to 3 or more and prove that $theta(G)=D(G)$ if and only if $G$ is asymmetric, $K_n$ or $overline{K_n}$. Finally, we consider the graphs in the Johnson scheme for their distinguishing numbers and thresholds.
Let d_i(G) be the density of the 3-vertex i-edge graph in a graph G, i.e., the probability that three random vertices induce a subgraph with i edges. Let S be the set of all quadruples (d_0,d_1,d_2,d_3) that are arbitrary close to 3-vertex graph densities in arbitrary large graphs. Huang, Linial, Naves, Peled and Sudakov have recently determined the projection of the set S to the (d_0,d_3) plane. We determine the projection of the set S to all the remaining planes.
We generalise the standard constructions of a Cayley graph in terms of a group presentation by allowing some vertices to obey different relators than others. The resulting notion of presentation allows us to represent every vertex transitive graph. As an intermediate step, we prove that every countably infinite, connected, vertex transitive graph has a perfect matching. Incidentally, we construct an example of a 2-ended cubic vertex transitive graph which is not a Cayley graph, answering a question of Watkins from 1990.
Given a simple undirected graph $G$ there is a simplicial complex $mathrm{Ind}(G)$, called the independence complex, whose faces correspond to the independent sets of $G$. This is a well studied concept because it provides a fertile ground for interactions between commutative algebra, graph theory and algebraic topology. One of the line of research pursued by many authors is to determine the graph classes for which the associated independence complex is Cohen-Macaulay. For example, it is known that when $G$ is a chordal graph the complex $mathrm{Ind}(G)$ is in fact vertex decomposable, the strongest condition in the Cohen-Macaulay ladder. In this article we consider a generalization of independence complex. Given $rgeq 1$, a subset of the vertex set is called $r$-independent if the connected components of the induced subgraph have cardinality at most $r$. The collection of all $r$-independent subsets of $G$ form a simplicial complex called the $r$-independence complex and is denoted by $mathrm{Ind}_r(G)$. It is known that when $G$ is a chordal graph the complex $mathrm{Ind}_r(G)$ has the homotopy type of a wedge of spheres. Hence it is natural to ask which of these complexes are shellable or even vertex decomposable. We prove, using Woodroofes chordal hypergraph notion, that these complexes are always shellable when the underlying chordal graph is a tree. Further, using the notion of vertex splittable ideals we show that for caterpillar graphs the associated $r$-independence complex is vertex decomposable for all values of $r$. We also construct chordal graphs on $2r+2$ vertices such that their $r$-independence complexes are not sequentially Cohen-Macaulay for any $r ge 2$.
Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds for graphs with small treewidth or small maximum average degree, including planar graphs. However, for dense graphs that are neither cliques nor 4-colorable, only asymptotic results are known. Here, we confirm the conjecture for threshold graphs, i.e. graphs that are both split graphs and cographs, and for co-chain graphs with both sides of the same size divisible by 4.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
