A graph G=(VG,EG) is said to be a cograph if the path P4 does not appear among its induced subgraphs. The vicinal preorder ≺ on the vertex set VG is defined in terms of inclusions between ...neighborhoods. The minimum number ∇(G) of ≺-chains required to cover G is called the Dilworth number of G. In this paper it is proved that for a cograph G, the multiplicity of every Seidel eigenvalue λ≠±1 does not exceed ∇(G). This bound turns out to be tight and can be further improved for threshold graphs. Moreover, it is shown that cographs with at least two vertices have no Seidel eigenvalues in the interval (−1,1).
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
A kernel of a directed graph is a subset of vertices that is both independent and absorbing (every vertex not in the kernel has an out-neighbour in the kernel).
Not all directed graphs contain ...kernels, and computing a kernel or deciding that none exist is NP-complete even on low-degree planar digraphs. The existing polynomial-time algorithms for this problem are all obtained by restricting both the undirected structure and the edge orientations of the input: for example, to chordal graphs without bidirectional edges (Pass-Lanneau, Igarashi and Meunier, Discrete Appl Math 2020) or to permutation graphs where each clique has a sink (Abbas and Saoula, 4OR 2005).
By contrast, we count the kernels of a fuzzy circular interval graph in polynomial time, regardless of its edge orientations, and return a kernel when one exists. (Fuzzy circular interval graphs were introduced by Chudnovsky and Seymour in their structure theorem for claw-free graphs.)
We also consider kernels on cographs, where we establish NP-hardness in general but linear-time solvability on the subclass of threshold graphs.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic traceability, and in this paper, we study the class of bounded clique-width graphs through the lens of ...succinct data structures. A data structure is said to be succinct if the amount of space used by the data structure is information-theoretically optimal up to lower-order additive terms. More specifically, we design a succinct data structure for graphs on n vertices whose clique-width is at most k≤ϵlogn for some constant 0<ϵ<1/6, that supports degree, adjacency, and neighborhood queries efficiently. This resolves an open problem of Kamali (Algorithmica-2018). As an application of our main technique, we also propose succinct data structures for distance-hereditary and Ptolemaic graphs, which are subclasses of the class of graphs with clique-width at most 3.
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 article, we examine the controllability of Laplacian dynamic networks on cographs. Cographs appear in modeling a wide range of networks and include as special instances, the threshold graphs. ...In this article, we present necessary and sufficient conditions for the controllability of cographs, and provide an efficient method for selecting a minimal set of input nodes from which the network is controllable. In particular, we define a sibling partition in a cograph and show that the network is controllable if all nodes of any cell of this partition except one are chosen as control nodes. The key ingredient for such characterizations is the intricate connection between the modularity of cographs and their modal properties. Finally, we use these results to characterize the controllability conditions for certain subclasses of cographs.
We continue to study coherent partitions of graphs whereby the vertex set is partitioned into subsets that induce biclique spanned subgraphs. The problem of identifying the minimum number of edges to ...obtain biclique spanned connected components (CNP), called the coherence number, is NP-hard even on bipartite graphs. Here, we propose a graph transformation geared towards obtaining an O(logn)-approximation algorithm for the CNP on a bipartite graph with n vertices. The transformation is inspired by a new characterization of biclique spanned subgraphs. In addition, we study coherent partitions on prime graphs, and show that finding coherent partitions reduces to the problem of finding coherent partitions in a prime graph. Therefore, these results provide future directions for approximation algorithms for the coherence number of a given graph.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
7.
Perfect Italian domination in cographs Banerjee, S.; Henning, Michael A.; Pradhan, D.
Applied mathematics and computation,
02/2021, Volume:
391
Journal Article
Peer reviewed
•We study the perfect Italian domination problem on cographs.•For a connected cograph G of order n ≥ 1, γIp(G)∈{1,2,3,4} or γIp(G)=n.•There is no connected cograph with γIp(G)=k, where k ∈ {5, 6, ...7, 8, 9}.•A linear time algorithm that computes γIp(G) for a cograph G is proposed.
For a graph G=(VG,EG), a perfect Italian dominating function on G is a function g: VG → {0, 1, 2} satisfying the condition that for each vertex v with g(v)=0, the sum of the function values assigned to the neighbors of v is exactly two, that is, ∑g(u)=2 where the sum is taken over all neighbors of v. The weight of g, denoted by w(g) is defined ∑g(v) where the sum is taken over all v ∈ VG. The perfect Italian domination number of G, denoted γIp(G), is the minimum weight of a perfect Italian dominating function of G. In this paper, we prove that the perfect Italian domination number of a connected cograph, a graph containing no induced path on four vertices, belongs to {1, 2, 3, 4} or equals to the order of the cograph. We prove that there is no connected cograph with perfect Italian domination number k, where k ∈ {5, 6, 7, 8, 9}. We also show that for any positive integer k, k ∉ {5, 6, 7, 8, 9}, there exists a connected cograph whose perfect Italian domination number is k. Moreover, we devise a linear time algorithm that computes the perfect Italian domination number in cographs.
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 problems of reconfigurability of independent sets in graphs. We consider three different models (token jumping, token sliding, and token addition and removal) and analyze relationships ...between them. We prove that independent set reconfigurability in perfect graphs (under any of the three models) generalizes the shortest path reconfigurability problem in general graphs and is therefore PSPACE-complete. On the positive side, we give polynomial results for even-hole-free graphs and P4-free graphs.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
The micro-world of cographs Alecu, Bogdan; Lozin, Vadim; de Werra, Dominique
Discrete Applied Mathematics,
05/2022, Volume:
312
Journal Article
Peer reviewed
Open access
Cographs constitute a small point in the atlas of graph classes. However, by zooming in on this point, we discover a complex world, where many parameters jump from finiteness to infinity. In the ...present paper, we identify several milestones in the world of cographs and create a hierarchy of graph parameters grounded on these milestones.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
10.
Graphon convergence of random cographs Stufler, Benedikt
Random structures & algorithms,
October 2021, 2021-10-00, 20211001, Volume:
59, Issue:
3
Journal Article
Peer reviewed
Open access
We study the behavior of random labeled and unlabeled cographs with n vertices as n tends to infinity. We show that both models admit a novel random graphon W1/2 as distributional limit. Our main ...tool is an enhanced skeleton decomposition of the random Pólya An tree with n leaves and no internal vertices having only one child. As a byproduct, we obtain limits describing the asymptotic shape of this model of random trees.
Full text
Available for:
FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SBCE, SBMB, UL, UM, UPUK
PDF
