Consider a graph G=(V,E).A perfect double Roman dominating function(PDRDF for short)is a function h:V→{0,1,2,3}that satisfies the condition∑_(y∈NG[x],h(y)≥1)h(y)=|{y∈NG(x):h(y)≥1}|+2 for any x∈V with h(x)≤1.Th...Consider a graph G=(V,E).A perfect double Roman dominating function(PDRDF for short)is a function h:V→{0,1,2,3}that satisfies the condition∑_(y∈NG[x],h(y)≥1)h(y)=|{y∈NG(x):h(y)≥1}|+2 for any x∈V with h(x)≤1.The weightω(h)of this function is∑_(y∈V)h(y).The perfect double Roman domination number(PDRD-number)of G,denoted byγ_(dR)^(p)(G),is defined as the minimum weight among all PDRDFs of G.This article presents a comprehensive analysis of the PDRD-number of connected cographs,demonstrating that it falls within the set{2,3,4,5,6}.Furthermore,it establishes that for any integer i≥7,there is a connected cograph G such that its PDRD-number is equal to i.展开更多
The distribution of Seidel eigenvalues of cographs is investigated in this paper.We prove that there is no Seidel eigenvalue of nontrivial cographs in the interval(−1,1).We also show the optimality of the interval(−1,...The distribution of Seidel eigenvalues of cographs is investigated in this paper.We prove that there is no Seidel eigenvalue of nontrivial cographs in the interval(−1,1).We also show the optimality of the interval(−1,1)in the sense that for any ε>0 either of the intervals(1,1+ε)and(−1−ε,−1)contains a Seidel eigenvalue of some cograph of order n when n is sufficiently large.展开更多
.The intersection power graph of a finite group G is a simple graph whose vertex set is G,in which two distinct vertices and y are adjacent if and only if either one of a and y is the identity element,or(a)n(y)is non-....The intersection power graph of a finite group G is a simple graph whose vertex set is G,in which two distinct vertices and y are adjacent if and only if either one of a and y is the identity element,or(a)n(y)is non-trivial.A number of important graph classes,including cographs,chordal graphs,split graphs,and threshold graphs,can be defined either structurally or in terms of forbidden induced subgraphs.In this paper,we characterize the finite groups whose intersection power graphs are cographs,split graphs,and threshold graphs.We also classify the finite nilpotent groups whose intersection power graphs are chordal.展开更多
Algorithms used in data mining and bioinformatics have to deal with huge amount of data efficiently. In many applications, the data are supposed to have explicit or implicit structures. To develop efficient algorithms...Algorithms used in data mining and bioinformatics have to deal with huge amount of data efficiently. In many applications, the data are supposed to have explicit or implicit structures. To develop efficient algorithms for such data, we have to propose possible structure models and test if the models are feasible. Hence, it is important to make a compact model for structured data, and enumerate all instances efficiently. There are few graph classes besides trees that can be used for a model. In this paper, we investigate distance-hereditary graphs. This class of graphs consists of isometric graphs and hence contains trees and cographs. First, a canonical and compact tree representation of the class is proposed. The tree representation can be constructed in linear time by using prefix trees. Usually, prefix trees are used to maintain a set of strings. In our algorithm, the prefix trees are used to maintain the neighborhood of vertices, which is a new approach unlike the lexicographically breadth-first search used in other studies. Based on the canonical tree representation, efficient algorithms for the distance-hereditary graphs are proposed, including linear time algorithms for graph recognition and graph isomorphism and an efficient enumeration algorithm. An efficient coding for the tree representation is also presented; it requires [3.59n] bits for a distance-hereditary graph of n vertices and 3n bits for a cograph. The results of coding improve previously known upper bounds （both are 2^O（nlogn）） of the number of distance-hereditary graphs and cographs to 2^[3.59n] and 2^3n, respectively.展开更多
基金Supported by the National Natural Science Foundation Youth Fund of China(Grant No.11701059)The Chongqing Natural Science Foundation Innovation and Development Joint Fund(Municipal Education Commission)(Grant No.CSTB2022NSCQ-LZX0003)The Open Research Fund of Key Laboratory of Nonlinear Analysis&Applications(Central China Normal University),Ministry of Education,P.R.China。
文摘Consider a graph G=(V,E).A perfect double Roman dominating function(PDRDF for short)is a function h:V→{0,1,2,3}that satisfies the condition∑_(y∈NG[x],h(y)≥1)h(y)=|{y∈NG(x):h(y)≥1}|+2 for any x∈V with h(x)≤1.The weightω(h)of this function is∑_(y∈V)h(y).The perfect double Roman domination number(PDRD-number)of G,denoted byγ_(dR)^(p)(G),is defined as the minimum weight among all PDRDFs of G.This article presents a comprehensive analysis of the PDRD-number of connected cographs,demonstrating that it falls within the set{2,3,4,5,6}.Furthermore,it establishes that for any integer i≥7,there is a connected cograph G such that its PDRD-number is equal to i.
基金Supported by the National Natural Science Foundation of China(Grant No.12001006)the Natural Science Foundation of Universities of Anhui Province(Grant No.2023AH050904).
文摘The distribution of Seidel eigenvalues of cographs is investigated in this paper.We prove that there is no Seidel eigenvalue of nontrivial cographs in the interval(−1,1).We also show the optimality of the interval(−1,1)in the sense that for any ε>0 either of the intervals(1,1+ε)and(−1−ε,−1)contains a Seidel eigenvalue of some cograph of order n when n is sufficiently large.
基金supported by the National Natural Science Foundation of China(Grant Nos.11801441,61976244)the Natural Science Basic Research Program of Shaanxi(Program No.2020JQ-761)the Shaanxi Fundamental Science Research Project for Mathematics and Physics(Grant No.22JSQ024).
文摘.The intersection power graph of a finite group G is a simple graph whose vertex set is G,in which two distinct vertices and y are adjacent if and only if either one of a and y is the identity element,or(a)n(y)is non-trivial.A number of important graph classes,including cographs,chordal graphs,split graphs,and threshold graphs,can be defined either structurally or in terms of forbidden induced subgraphs.In this paper,we characterize the finite groups whose intersection power graphs are cographs,split graphs,and threshold graphs.We also classify the finite nilpotent groups whose intersection power graphs are chordal.
基金presented at the 4th Annual Conference on Theory and Applications of Models of Computation(TAMC07)
文摘Algorithms used in data mining and bioinformatics have to deal with huge amount of data efficiently. In many applications, the data are supposed to have explicit or implicit structures. To develop efficient algorithms for such data, we have to propose possible structure models and test if the models are feasible. Hence, it is important to make a compact model for structured data, and enumerate all instances efficiently. There are few graph classes besides trees that can be used for a model. In this paper, we investigate distance-hereditary graphs. This class of graphs consists of isometric graphs and hence contains trees and cographs. First, a canonical and compact tree representation of the class is proposed. The tree representation can be constructed in linear time by using prefix trees. Usually, prefix trees are used to maintain a set of strings. In our algorithm, the prefix trees are used to maintain the neighborhood of vertices, which is a new approach unlike the lexicographically breadth-first search used in other studies. Based on the canonical tree representation, efficient algorithms for the distance-hereditary graphs are proposed, including linear time algorithms for graph recognition and graph isomorphism and an efficient enumeration algorithm. An efficient coding for the tree representation is also presented; it requires [3.59n] bits for a distance-hereditary graph of n vertices and 3n bits for a cograph. The results of coding improve previously known upper bounds （both are 2^O（nlogn）） of the number of distance-hereditary graphs and cographs to 2^[3.59n] and 2^3n, respectively.
