A canonical double cover B(X) of a graph X is the direct product of X and the complete graph K2 on two vertices. In order to answer the question when a canonical double cover of a given graph is a ...Cayley graph, in 1992 Marušič et al. introduced the concept of generalized Cayley graphs. In this paper this concept is generalized to a wider class of graphs, the so-called extended generalized Cayley graphs. It is proved that the canonical double cover of a connected non-bipartite graph X is a Cayley graph if and only if X is an extended generalized Cayley graph. This corrects an incorrectly stated claim in Discrete Math. 102 (1992), 279–285.
A clique (resp, independent set) in a graph is strong if it intersects every maximal independent set (resp, every maximal clique). A graph is clique intersect stable set (CIS) if all of its maximal ...cliques are strong and localizable if it admits a partition of its vertex set into strong cliques. In this paper we prove that a clique
C in a vertex‐transitive graph
Γ is strong if and only if
∣
C
∣
∣
I
∣
=
∣
V
(
Γ
)
∣ for every maximal independent set
I of
Γ. On the basis of this result we prove that a vertex‐transitive graph is CIS if and only if it admits a strong clique and a strong independent set. We classify all vertex‐transitive graphs of valency at most 4 admitting a strong clique, and give a partial characterization of 5‐valent vertex‐transitive graphs admitting a strong clique. Our results imply that every vertex‐transitive graph of valency at most 5 that admits a strong clique is localizable. We answer an open question by providing an example of a vertex‐transitive CIS graph which is not localizable.
Abstract
A graph is said to be
unstable
if the direct product (also called the
canonical double cover
of ) has automorphisms that do not come from automorphisms of its factors and . It is
...nontrivially unstable
if it is unstable, connected, nonbipartite, and distinct vertices have distinct sets of neighbours. In this paper, we prove two sufficient conditions for stability of graphs in which every edge lies on a triangle, revising an incorrect claim of Surowski and filling in some gaps in the proof of another one. We also consider triangle‐free graphs, and prove that there are no nontrivially unstable triangle‐free graphs of diameter 2. An interesting construction of nontrivially unstable graphs is given and several open problems are posed.
A graph Γ is said to be distance-balanced if for any edge uv of Γ, the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u, and it is called nicely ...distance-balanced if in addition this number is independent of the chosen edge uv. A graph Γ is said to be strongly distance-balanced if for any edge uv of Γ and any integer k, the number of vertices at distance k from u and at distance k+1 from v is equal to the number of vertices at distance k+1 from u and at distance k from v.
In this paper we solve an open problem posed by Kutnar and Miklavič (2014) by constructing several infinite families of nonbipartite nicely distance-balanced graphs which are not strongly distance-balanced. We disprove a conjecture regarding characterization of strongly distance-balanced graphs posed by Balakrishnan et al. (2009) by providing infinitely many counterexamples, and answer a question posed by Kutnar et al. in (2006) regarding the existence of semisymmetric distance-balanced graphs which are not strongly distance-balanced by providing an infinite family of such examples. We also show that for a graph Γ with n vertices and m edges it can be checked in O(mn) time if Γ is strongly-distance balanced and if Γ is nicely distance-balanced.
It is known that there are precisely three transitive permutation groups of degree 6 that admit an invariant partition with three parts of size 2 such that the kernel of the action on the parts has ...order 4; these groups are called
A
4
(
6
),
S
4
(
6
d
) and
S
4
(
6
c
). For each
L
∈
{
A
4
(
6
)
,
S
4
(
6
d
)
,
S
4
(
6
c
)
}, we construct an infinite family of finite connected 6‐valent graphs
{
Γ
n
}
n
∈
N and arc‐transitive groups
G
n
≤
Aut
(
Γ
n
) such that the permutation group induced by the action of the vertex‐stabiliser
(
G
n
)
v on the neighbourhood of a vertex
v is permutation isomorphic to
L, and such that
∣
(
G
n
)
v
∣ is exponential in
∣
V
(
Γ
n
)
∣. These three groups were the only transitive permutation groups of degree at most 7 for which the existence of such a family was undecided. In the process, we construct an infinite family of cubic 2‐arc‐transitive graphs such that the dimension of the 1‐eigenspace over the field of order 2 of the adjacency matrix of the graph grows linearly with the order of the graph.
A clique in a graph is strong if it intersects all maximal independent sets. A graph is localizable if it has a partition of the vertex set into strong cliques. Localizable graphs were introduced by ...Yamashita and Kameda in 1999 and form a rich class of well-covered graphs that coincides with the class of well-covered graphs within the class of perfect graphs. In this paper, we give several equivalent formulations of the property of localizability and develop polynomially testable characterizations of localizable graphs within three non-perfect graph classes: triangle-free graphs, C4-free graphs, and line graphs. Furthermore, we use localizable graphs to construct an infinite family of counterexamples to a conjecture due to Zaare-Nahandi about k-partite well-covered graphs having all maximal cliques of size k.
Detecting strong cliques Hujdurović, Ademir; Milanič, Martin; Ries, Bernard
Discrete mathematics,
September 2019, 2019-09-00, Letnik:
342, Številka:
9
Journal Article
Recenzirano
Odprti dostop
A strong clique in a graph is a clique intersecting every maximal independent set. We study the computational complexity of six algorithmic decision problems related to strong cliques in graphs and ...almost completely determine their complexity in the classes of chordal graphs, weakly chordal graphs, line graphs and their complements, and graphs of maximum degree at most three. Our results rely on connections with matchings and relate to several graph properties studied in the literature, including well-covered graphs, localizable graphs, and general partition graphs.
For a permutation group G acting on a set V, a subset I of G is said to be an intersecting set if for every pair of elements g,h∈I there exists v∈V such that g(v)=h(v). The intersection densityρ(G) ...of a transitive permutation group G is the maximum value of the quotient |I|/|Gv| where Gv is a stabilizer of a point v∈V and I runs over all intersecting sets in G. If Gv is the largest intersecting set in G then G is said to have the Erdős–Ko–Rado (EKR)-property, and moreover, G has the strict-EKR-property if every intersecting set of maximum size in G is a coset of a point stabilizer. Intersecting sets in G coincide with independent sets in the so-called derangement graphΓG, defined as the Cayley graph on G with connection set consisting of all derangements, that is, fixed-point free elements of G. In this paper a conjecture regarding the existence of transitive permutation groups whose derangement graphs are complete multipartite graphs, posed by Meagher, Razafimahatratra and Spiga in Meagher et al. (2021) is proved. The proof uses direct product of groups. Questions regarding maximum intersecting sets in direct and wreath products of groups and the (strict)-EKR-property of these group products are also investigated. In addition, some errors appearing in the literature on this topic are corrected.
PDF
