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.
For an edge
$uv$
in a graph
$G$
,
$W_{u,v}^{G}$
denotes the set of all vertices of
$G$
that are closer to
$u$
than to
$v$
. A graph
$G$
is said to be quasi-distance-balanced if there exists a ...constant
$\unicodeSTIX{x1D706}>1$
such that
$|W_{u,v}^{G}|=\unicodeSTIX{x1D706}^{\pm 1}|W_{v,u}^{G}|$
for every pair of adjacent vertices
$u$
and
$v$
. The existence of nonbipartite quasi-distance-balanced graphs is an open problem. In this paper we investigate the possible structure of cycles in quasi-distance-balanced graphs and generalise the previously known result that every quasi-distance-balanced graph is triangle-free. We also prove that a connected quasi-distance-balanced graph admitting a bridge is isomorphic to a star. Several open problems are posed.
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.
On normality of n-Cayley graphs Hujdurović, Ademir; Kutnar, Klavdija; Marušič, Dragan
Applied mathematics and computation,
09/2018, Volume:
332
Journal Article
Peer reviewed
Let G be a finite group and X a (di)graph. If there exists a semiregular subgroup G¯ of the automorphism group Aut(X) isomorphic to G with n orbits on V(X) then the (di)graph X is called an n-Cayley ...graph on G. If, in addition, this subgroup G¯ is normal in Aut(X) then X is called a normal n-Cayley graph on G.
In this paper the normalizers of semiregular subgroups of the automorphism group of a digraph are characterized. It is proved that every finite group admits a vertex-transitive normal n-Cayley graph for every n ≥ 2. For the most part the graphs are constructed as Cartesian product of graphs. It is proved that a Cartesian product of two relatively prime graphs is Cayley (resp. normal Cayley) if and only if the factor graphs are Cayley (resp. normal Cayley). In addition, the concept of graphical regular representations (GRRs) is generalized to n-GRR in a natural way, and it is proved that any group admitting a GRR also admits an n-GRR for any n ≥ 1.
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, Volume:
342, Issue:
9
Journal Article
Peer reviewed
Open access
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.
PDF
