Almost controllable graphs and beyond Du, Zenan; You, Lihua; Liu, Hechao
Discrete mathematics,
January 2024, 2024-01-00, Letnik:
347, Številka:
1
Journal Article
Recenzirano
Odprti dostop
An eigenvalue λ of a graph G of order n is a main eigenvalue if its eigenspace is not orthogonal to the all-ones vector jn. In 1978, Cvetković proved that G has exactly one main eigenvalue if and ...only if G is regular, and posed the following long-standing problem: characterize the graphs with exactly k(2≤k≤n) main eigenvalues. Graphs of order n with n, n−1 main eigenvalues are called controllable, almost controllable, respectively. Cographs, threshold graphs are frequently studied in structural graph theory and computer science. In this paper, all almost controllable cographs, all almost controllable threshold graphs and all almost controllable graphs with second largest eigenvalue less than or equal to 5−12 are characterized. Furthermore, we give some results about cographs with exactly n−2 main eigenvalues, and propose some additional problems for further study.
A vertex subset S of a graph G is a general position set of G if no vertex of S lies on a geodesic between two other vertices of S. The cardinality of a largest general position set of G is the ...general position number gp(G) of G. It is proved that S⊆V(G) is in general position if and only if the components of GS are complete subgraphs, the vertices of which form an in-transitive, distance-constant partition of S. If diam(G)=2, then gp(G) is the maximum of ω(G) and the maximum order of an induced complete multipartite subgraph of the complement of G. As a consequence, gp(G) of a cograph G can be determined in polynomial time. If G is bipartite, then gp(G) ≤ α(G) with equality if diam(G) ∈ {2, 3}. A formula for the general position number of the complement of an arbitrary bipartite graph is deduced and simplified for the complements of trees, of grids, and of hypercubes.
Phylogenomics with paralogs Hellmuth, Marc; Wieseke, Nicolas; Lechner, Marcus ...
Proceedings of the National Academy of Sciences - PNAS,
02/2015, Letnik:
112, Številka:
7
Journal Article
Recenzirano
Odprti dostop
Phylogenomics heavily relies on well-curated sequence data sets that comprise, for each gene, exclusively 1:1 orthologos. Paralogs are treated as a dangerous nuisance that has to be detected and ...removed. We show here that this severe restriction of the data sets is not necessary. Building upon recent advances in mathematical phylogenetics, we demonstrate that gene duplications convey meaningful phylogenetic information and allow the inference of plausible phylogenetic trees, provided orthologs and paralogs can be distinguished with a degree of certainty. Starting from tree-free estimates of orthology, cograph editing can sufficiently reduce the noise to find correct event-annotated gene trees. The information of gene trees can then directly be translated into constraints on the species trees. Although the resolution is very poor for individual gene families, we show that genome-wide data sets are sufficient to generate fully resolved phylogenetic trees, even in the presence of horizontal gene transfer.
Significance We demonstrate that the distribution of paralogs in large gene families contains in itself sufficient phylogenetic signal to infer fully resolved species phylogenies. This source of phylogenetic information is independent of information contained in orthologous sequences and is resilient against horizontal gene transfer. An important consequence is that phylogenomics data sets need not be restricted to 1:1 orthologs.
Aharoni and Korman (1992) 3 conjectured that every ordered set with no infinite antichains possesses a chain and a partition into antichains so that each part intersects the chain.
The conjecture is ...verified for posets whose incomparability graph is locally finite. It follows that the conjecture is true for (3+1)-free posets with no infinite antichains.
We give a necessary and sufficient condition for a P4-free graph to be a cograph. This allows us to obtain a simple proof of the fact that finite P4-free graphs are finite cographs. We also prove that N-free chain complete posets and N-free posets with no infinite antichains are series-parallel.
As a consequence, we obtain that the conjecture is true for N-free posets with no infinite antichain.
A graph is a cograph if and only if it has no induced path on 4 vertices. The twin reduction graph of a graph G is denoted by RG. In this article, we describe the Laplacian eigenvalues and ...eigenvectors of a cograph G using its twin reduction graph RG, and characterize cographs with even and odd integer eigenvalues, respectively. We provide a construction for the Laplacian cospectral cographs. Further, we provide a complete description of the Laplacian spectrum of H-join of graphs when H is a cograph, and then obtain bounds for the algebraic connectivity of such graphs. We also provide some interesting observations on Hadamard diagonalizable cographs.
Graphs defined on groups Peter J. Cameron
International journal of group theory,
06/2022, Letnik:
11, Številka:
2
Journal Article
Odprti dostop
This paper concerns aspects of various graphs whose vertex set is a group $G$ and whose edges reflect group structure in some way (so that, in particular, they are invariant under the action ...of the automorphism group of $G$). The particular graphs I will chiefly discuss are the power graph, enhanced power graph, deep commuting graph, commuting graph, and non-generating graph.My main concern is not with properties of these graphs individually, but rather with comparisons between them. The graphs mentioned, together with the null and complete graphs, form a hierarchy (as long as $G$ is non-abelian), in the sense that the edge set of any one is contained in that of the next; interesting questions involve when two graphs in the hierarchy are equal, or what properties the difference between them has. I also consider various properties such as universality and forbidden subgraphs,comparing how these properties play out in the different graphs.I have also included some results on intersection graphs of subgroups of various types, which are often in a ''dual'' relation to one of the other graphs considered. Another actor is the Gruenberg--Kegel graph, or prime graph, of a group: this very small graph has a surprising influence over various graphs defined on the group.Other graphs which have been proposed, such as the nilpotence, solvability, and Engel graphs, will be touched on rather more briefly. My emphasis is on finite groups but there is a short section on results for infinite groups. There are briefer discussions of general $Aut(G)$-invariant graphs, and structures other than groups (such as semigroups and rings).Proofs, or proof sketches, of known results have been included where possible. Also, many open questions are stated, in the hope of stimulating further investigation.
A P4-free graph is called a cograph. In this paper we partially characterize finite groups whose power graph is a cograph. As we will see, this problem is a generalization of the determination of ...groups in which every element has prime power order, first raised by Graham Higman in 1957 and fully solved very recently.
First we determine all groups G and H for which the power graph of G×H is a cograph. We show that groups whose power graph is a cograph can be characterised by a condition only involving elements whose orders are prime or the product of two (possibly equal) primes. Some important graph classes are also taken under consideration. For finite simple groups we show that in most of the cases their power graphs are not cographs: the only ones for which the power graphs are cographs are certain groups PSL(2,q) and Sz(q) and the group PSL(3,4). However, a complete determination of these groups involves some hard number-theoretic problems.
In this note, we list some propositions of the perfect Roman domination number of graphs and give the characterization of graphs G with special value of the perfect Roman domination. Furthermore, ...γRp(F)+γRp(F¯) is given. At the last, a linear time algorithm is shown to compute the perfect Roman domination number of a cograph.
The modular decomposition of a graph G is a natural construction to capture key features of G in terms of a labeled tree (T,t) whose vertices are labeled as “series” (1), “parallel” (0) or “prime”. ...However, full information of G is provided by its modular decomposition tree (T,t) only, if G is a cograph, i.e., G does not contain prime modules. In this case, (T,t) explains G, i.e., {x,y}∈E(G) if and only if the lowest common ancestor lcaT(x,y) of x and y has label “1”. Pseudo-cographs, or, more generally, GaTEx graphs G are graphs that can be explained by labeled galled-trees, i.e., labeled networks (N,t) that are obtained from the modular decomposition tree (T,t) of G by replacing the prime vertices in T by simple labeled cycles. GaTEx graphs can be recognized and labeled galled-trees that explain these graphs can be constructed in linear time.
In this contribution, we provide a novel characterization of GaTEx graphs in terms of a set FGT of 25 forbidden induced subgraphs. This characterization, in turn, allows us to show that GATEX graphs are closely related to many other well-known graph classes such as P4-sparse and P4-reducible graphs, weakly-chordal graphs, perfect graphs with perfect order, comparability and permutation graphs, murky graphs as well as interval graphs, Meyniel graphs or very strongly-perfect and brittle graphs. Moreover, we show that every GATEX graph as twin-width at most 1.
We introduce the Maker–Breaker domination game, a two player game on a graph. At his turn, the first player, Dominator, selects a vertex in order to dominate the graph while the other player, ...Staller, forbids a vertex to Dominator in order to prevent him to reach his goal. Both players play alternately without missing their turn. This game is a particular instance of the so-called Maker–Breaker games, that is studied here in a combinatorial context. In this paper, we first prove that deciding the winner of the Maker–Breaker domination game is pspace-complete, even for bipartite graphs and split graphs. It is then showed that the problem is polynomial for cographs and trees. In particular, we define a strategy for Dominator that is derived from a variation of the dominating set problem, called the pairing dominating set problem.
PDF
