Cographs and 1-Sums Singh, Jagdeep
Graphs and combinatorics,
02/2024, Volume:
40, Issue:
1
Journal Article
Peer reviewed
A graph that can be generated from
K
1
using joins and 0-sums is called a cograph. We define a sesquicograph to be a graph that can be generated from
K
1
using joins, 0-sums, and 1-sums. We show ...that, like cographs, sesquicographs are closed under induced minors. Cographs are precisely the graphs that do not have the 4-vertex path as an induced subgraph. We obtain an analogue of this result for sesquicographs, that is, we find those non-sesquicographs for which every proper induced subgraph is a sesquicograph.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
Motivated by the linear time algorithm that locates the eigenvalues of a cograph G (Jacobs et al., 2017), we investigate the multiplicity of eigenvalue λ for λ≠0,−1. For cographs with balanced ...cotrees we determine explicitly the highest value for the multiplicity. The energy of a graph is defined as the sum of absolute values of the eigenvalues. A graph G on n vertices is said to be borderenergetic if its energy equals the energy of the complete graph Kn. We present families of non-cospectral and borderenergetic cographs.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Cograph generation with linear delay Jones, Átila A.; Protti, Fábio; Del-Vecchio, Renata R.
Theoretical computer science,
02/2018, Volume:
713
Journal Article
Peer reviewed
Open access
Cographs have always been a research target in areas such as coloring, graph decomposition, and spectral theory. In this work, we present an algorithm to generate all unlabeled cographs with n ...vertices, based on the generation of cotrees. The delay of our algorithm (time spent between two consecutive outputs) is O(n). The time needed to generate the first output is also O(n), which gives an overall O(nMn) time complexity, where Mn is the number of unlabeled cographs with n vertices. The algorithm avoids the generation of duplicates (isomorphic outputs) and produces, as a by-product, a linear ordering of unlabeled cographs with n vertices.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
•We study the secure domination problem in cographs.•The secure domination problem is NP-hard for circle graphs.•An O(n+m) time algorithm is proposed to find the secure domination number of a given ...cograph.
Let G=(V,E) be a graph. A subset D of vertices of G is called a dominating set of G if for every u∈V∖D, there exists a vertex v∈D such that uv∈E. A dominating set D of a graph G is called a secure dominating set of G if for every u∈V∖D, there exists a vertex v∈D such that uv∈E and (D∖{v})∪{u} is a dominating set of G. The secure domination number of G, denoted by γs(G), is the minimum cardinality of a secure dominating set of G. In this paper, we present an O(n+m) time algorithm to compute the secure domination number of a cograph having n vertices and m edges.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
A lid-coloring (locally identifying coloring) of a graph is a proper coloring such that, for any edge uv, if u and v have distinct closed neighborhoods, then the set of colors used on vertices of the ...closed neighborhoods of u and v are distinct. The lid-chromatic number is the minimum number of colors used in a lid-coloring. In this paper we prove a relation between lid-coloring and a variation, called strong lid-coloring. With this, we obtain linear time algorithms to calculate the lid-chromatic number for some classes of graphs with few P4's, such as cographs, P4-sparse graphs and (q,q−4)-graphs. We also prove that the lid-chromatic number is O(n1−ε)-inapproximable in polynomial time for every ε>0, unless P=NP.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Interval graphs and proper interval graphs are well known graph classes, for which several generalizations have been proposed in the literature. In this work, we study the (proper) thinness, and ...several variations, for the classes of cographs, crowns graphs and grid graphs. We provide the exact values for several variants of thinness (proper, independent, complete, precedence, and combinations of them) for the crown graphs CR n . For cographs, we prove that the precedence thinness can be determined in polynomial time. We also improve known bounds for the thinness of n × n grids GR n and m×n grids GR m,n , proving that n −1/3 ≤ thin(GR n ) ≤ n +1/2. Regarding the precedence thinness, we prove that prec-thin(GR n ,2 ) = n +1/2 and that n − 1 + 3/2 ≤ prec-thin(GR n ) ≤ n − 1 2. As applications, we show that the k -coloring problem is NP-complete for precedence 2-thin graphs and for proper 2-thin graphs, when k is part of the input. On the positive side, it is polynomially solvable for precedence proper 2-thin graphs, given the order and partition.
For a fixed number of colors, we show that, in node-weighted split graphs, cographs, and graphs of bounded tree-width, one can determine in polynomial time whether a proper list-coloring of the ...vertices of a graph such that the total weight of vertices of each color equals a given value in each part of a fixed partition of the vertices exists. We also show that this result is tight in some sense, by providing hardness results for the cases where any one of the assumptions does not hold. The edge-coloring variant is also studied, as well as special cases of cographs and split graphs.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
In this paper, we investigate a variant of Ramsey numbers called defective Ramsey numbers where cliques and independent sets are generalized to
k
-dense and
k
-sparse sets, both commonly called
k
...-defective sets. We focus on the computation of defective Ramsey numbers restricted to some subclasses of perfect graphs. Since direct proof techniques are often insufficient for obtaining new values of defective Ramsey numbers, we provide a generic algorithm to compute defective Ramsey numbers in a given target graph class. We combine direct proof techniques with our efficient graph generation algorithm to compute several new defective Ramsey numbers in perfect graphs, bipartite graphs and chordal graphs. We also initiate the study of a related parameter, denoted by
c
k
G
(
m
)
, which is the maximum order
n
such that the vertex set of any graph of order
n
in a class
G
can be partitioned into at most
m
subsets each of which is
k
-defective. We obtain several values for
c
k
G
(
m
)
in perfect graphs and cographs.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
Let
G
be a graph. If
u
,
v
∈
V
(
G
)
, a
u
–
v
shortest path of
G
is a path linking
u
and
v
with minimum number of edges. The
closed interval
I
u
,
v
consists of all vertices lying in some
u
–
v
...shortest path of
G
. For
S
⊆
V
(
G
)
, the set
I
S
is the union of all sets
I
u
,
v
for
u
,
v
∈
S
. We say that
S
is a
convex set if
I
S
=
S
. The
convex hull of
S
, denoted
I
h
S
, is the smallest convex set containing
S
. A set
S
is a
hull set of
G
if
I
h
S
=
V
(
G
)
. The cardinality of a minimum hull set of
G
is the
hull number of
G
, denoted by
h
n
(
G
)
. In this work we prove that deciding whether
h
n
(
G
)
≤
k
is NP-complete.We also present polynomial-time algorithms for computing
h
n
(
G
)
when
G
is a unit interval graph, a cograph or a split graph.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Let
G
=
(
V
,
E
)
be a graph with no isolated vertices. A vertex
v
totally dominates a vertex
w
(
w
≠
v
), if
v
is adjacent to
w
. A set
D
⊆
V
called a
total dominating set
of
G
if every vertex
v
∈
V
...is totally dominated by some vertex in
D
. The minimum cardinality of a total dominating set is the
total domination number
of
G
and is denoted by
γ
t
(
G
)
. A
total dominator coloring
of graph
G
is a proper coloring of vertices of
G
, so that each vertex totally dominates some color class. The total dominator chromatic number
χ
td
(
G
)
of
G
is the least number of colors required for a total dominator coloring of
G
. The
Total Dominator Coloring
problem is to find a total dominator coloring of
G
using the minimum number of colors. It is known that the decision version of this problem is NP-complete for general graphs. We show that it remains NP-complete even when restricted to bipartite, planar and split graphs. We further study the
Total Dominator Coloring
problem for various graph classes, including trees, cographs and chain graphs. First, we characterize the trees having
χ
td
(
T
)
=
γ
t
(
T
)
+
1
, which completes the characterization of trees achieving all possible values of
χ
td
(
T
)
. Also, we show that for a cograph
G
,
χ
td
(
G
)
can be computed in linear-time. Moreover, we show that
2
≤
χ
td
(
G
)
≤
4
for a chain graph
G
and then we characterize the class of chain graphs for every possible value of
χ
td
(
G
)
in linear-time.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
PDF
