Research on the independence polynomial of graphs has been very active.However,the computational complexity of determining independence polynomials for general graphs remains NP-hard.Letα(G)be the independence number...Research on the independence polynomial of graphs has been very active.However,the computational complexity of determining independence polynomials for general graphs remains NP-hard.Letα(G)be the independence number of G and i(G;k)be the number of independent sets of order k in G,then the independence polynomial is defined as I(G;x)=∑_(k=0)^(α(G))i(G;k)x^(k),i(G;0)=1.In this paper,by utilizing the transfer matrix,we obtain an analytical expression for I(CGn;x)of mono-cylindrical grid graphs CGn and present a crucial proof of it.Moreover,we also explore the Merrifield-Simmons index and other properties of CGn.展开更多
Let G(V, E) be a finite connected simple graph with vertex set V(G). A function is a signed dominating function f : <em style="white-space:normal;">V<span style="white-space:normal;"&...Let G(V, E) be a finite connected simple graph with vertex set V(G). A function is a signed dominating function f : <em style="white-space:normal;">V<span style="white-space:normal;">(<em style="white-space:normal;">G<span style="white-space:normal;">)<span style="white-space:nowrap;">→{<span style="white-space:nowrap;"><span style="white-space:nowrap;">−1,1} if for every vertex v <span style="white-space:nowrap;">∈ V(G), the sum of closed neighborhood weights of v is greater or equal to 1. The signed domination number γ<sub>s</sub>(G) of G is the minimum weight of a signed dominating function on G. In this paper, we calculate the signed domination numbers of the Cartesian product of two paths P<sub>m</sub> and P<sub>n</sub> for m = 6, 7 and arbitrary n.展开更多
With the development of information technology, the amount of power grid topology data has gradually increased. Therefore, accurate querying of this data has become particularly important. Several researchers have cho...With the development of information technology, the amount of power grid topology data has gradually increased. Therefore, accurate querying of this data has become particularly important. Several researchers have chosen different indexing methods in the filtering stage to obtain more optimized query results because currently there is no uniform and efficient indexing mechanism that achieves good query results. In the traditional algorithm, the hash table for index storage is prone to "collision" problems, which decrease the index construction efficiency. Aiming at the problem of quick index entry, based on the construction of frequent subgraph indexes, a method of serialized storage optimization based on multiple hash tables is proposed. This method mainly uses the exploration sequence to make the keywords evenly distributed; it avoids conflicts of the stored procedure and performs a quick search of the index. The proposed algorithm mainly adopts the "filterverify" mechanism; in the filtering stage, the index is first established offline, and then the frequent subgraphs are found using the "contains logic" rule to obtain the candidate set. Experimental results show that this method can reduce the time and scale of candidate set generation and improve query efficiency.展开更多
Let γ f(G) and γ~t f(G) be the fractional domination number and fractional total domination number of a graph G respectively. Hare and Stewart gave some exact fractional domination number of P n...Let γ f(G) and γ~t f(G) be the fractional domination number and fractional total domination number of a graph G respectively. Hare and Stewart gave some exact fractional domination number of P n×P m (grid graph) with small n and m . But for large n and m , it is difficult to decide the exact fractional domination number. Motivated by this, nearly sharp upper and lower bounds are given to the fractional domination number of grid graphs. Furthermore, upper and lower bounds on the fractional total domination number of strong direct product of graphs are given.展开更多
A set <em>S ⊆ V (G)</em> is called a geodetic set if every vertex of <em>G</em> lies on a shortest <em>u-v</em> path for some <em>u, v ∈ S</em>, the minimum cardinality...A set <em>S ⊆ V (G)</em> is called a geodetic set if every vertex of <em>G</em> lies on a shortest <em>u-v</em> path for some <em>u, v ∈ S</em>, the minimum cardinality among all geodetic sets is called geodetic number and is denoted by <img src="Edit_82259359-0135-4a65-9378-b767f0405b48.png" alt="" />. A set <em>C ⊆ V (G)</em> is called a chromatic set if <em>C</em> contains all vertices of different colors in<em> G</em>, the minimum cardinality among all chromatic sets is called the chromatic number and is denoted by <img src="Edit_d849148d-5778-459b-abbb-ff25b5cd659b.png" alt="" />. A geo-chromatic set<em> S</em><sub><em>c</em></sub><em> ⊆ V (G</em><em>)</em> is both a geodetic set and a chromatic set. The geo-chromatic number <img src="Edit_505e203c-888c-471c-852d-4b9c2dd1a31c.png" alt="" /><em> </em>of<em> G</em> is the minimum cardinality among all geo-chromatic sets of<em> G</em>. In this paper, we determine the geodetic number and the geo-chromatic number of 2-cartesian product of some standard graphs like complete graphs, cycles and paths.展开更多
A dominating set of a graph G is a set of vertices that contains at least one endpoint of every edge on the graph. The domination number of G is the order of a minimum dominating set of G. The (t, r) broadcast dominat...A dominating set of a graph G is a set of vertices that contains at least one endpoint of every edge on the graph. The domination number of G is the order of a minimum dominating set of G. The (t, r) broadcast domination is a generalization of domination in which a set of broadcasting vertices emits signals of strength t that decrease by 1 as they traverse each edge, and we require that every vertex in the graph receives a cumulative signal of at least r from its set of broadcasting neighbors. In this paper, we extend the study of (t, r) broadcast domination to directed graphs. Our main result explores the interval of values obtained by considering the directed (t, r) broadcast domination numbers of all orientations of a graph G. In particular, we prove that in the cases r = 1 and (t, r) = (2, 2), for every integer value in this interval, there exists an orientation of G which has directed (t, r) broadcast domination number equal to that value. We also investigate directed (t, r) broadcast domination on the finite grid graph, the star graph, the infinite grid graph, and the infinite triangular lattice graph. We conclude with some directions for future study.展开更多
对于“双高”电力系统的安全稳定运行而言,快速且准确的暂态功角稳定评估(transient angle stability assessment,TASA)方法至关重要。该文提出一种考虑并网变流器(grid side converter,GSC)切换控制特性且适用多新能源并网场景的TASA...对于“双高”电力系统的安全稳定运行而言,快速且准确的暂态功角稳定评估(transient angle stability assessment,TASA)方法至关重要。该文提出一种考虑并网变流器(grid side converter,GSC)切换控制特性且适用多新能源并网场景的TASA方法。首先,建立了“双高”电力系统的异质图模型(heterogenous information network model based on power system,HINPS),引入GSC二次侧控制参数构建HINPS中GSC节点的特征向量;然后,构建了异质时空神经网络(heterogenous spatial-temporal neural network,HSTN),其中图神经网络和循环神经网络的级联结构和差异化的节点特征聚合策略有效提高了模型的信息提取能力。IEEE-39节点和IEEE-300节点系统的实验结果表明,该方法可以准确评估系统的暂态功角稳定性,并表现出良好的泛化性能,具备在大规模电网中应用的潜力。展开更多
基金Supported by National Natural Science Foundation of China(Grant No.U20A20228)Huzhou Science and Technology Plan Project(Grant No.2022YZ53).
文摘Research on the independence polynomial of graphs has been very active.However,the computational complexity of determining independence polynomials for general graphs remains NP-hard.Letα(G)be the independence number of G and i(G;k)be the number of independent sets of order k in G,then the independence polynomial is defined as I(G;x)=∑_(k=0)^(α(G))i(G;k)x^(k),i(G;0)=1.In this paper,by utilizing the transfer matrix,we obtain an analytical expression for I(CGn;x)of mono-cylindrical grid graphs CGn and present a crucial proof of it.Moreover,we also explore the Merrifield-Simmons index and other properties of CGn.
文摘Let G(V, E) be a finite connected simple graph with vertex set V(G). A function is a signed dominating function f : <em style="white-space:normal;">V<span style="white-space:normal;">(<em style="white-space:normal;">G<span style="white-space:normal;">)<span style="white-space:nowrap;">→{<span style="white-space:nowrap;"><span style="white-space:nowrap;">−1,1} if for every vertex v <span style="white-space:nowrap;">∈ V(G), the sum of closed neighborhood weights of v is greater or equal to 1. The signed domination number γ<sub>s</sub>(G) of G is the minimum weight of a signed dominating function on G. In this paper, we calculate the signed domination numbers of the Cartesian product of two paths P<sub>m</sub> and P<sub>n</sub> for m = 6, 7 and arbitrary n.
基金supported by the State Grid Science and Technology Project (Title: Research on High Performance Analysis Technology of Power Grid GIS Topology Based on Graph Database, 5455HJ160005)
文摘With the development of information technology, the amount of power grid topology data has gradually increased. Therefore, accurate querying of this data has become particularly important. Several researchers have chosen different indexing methods in the filtering stage to obtain more optimized query results because currently there is no uniform and efficient indexing mechanism that achieves good query results. In the traditional algorithm, the hash table for index storage is prone to "collision" problems, which decrease the index construction efficiency. Aiming at the problem of quick index entry, based on the construction of frequent subgraph indexes, a method of serialized storage optimization based on multiple hash tables is proposed. This method mainly uses the exploration sequence to make the keywords evenly distributed; it avoids conflicts of the stored procedure and performs a quick search of the index. The proposed algorithm mainly adopts the "filterverify" mechanism; in the filtering stage, the index is first established offline, and then the frequent subgraphs are found using the "contains logic" rule to obtain the candidate set. Experimental results show that this method can reduce the time and scale of candidate set generation and improve query efficiency.
文摘Let γ f(G) and γ~t f(G) be the fractional domination number and fractional total domination number of a graph G respectively. Hare and Stewart gave some exact fractional domination number of P n×P m (grid graph) with small n and m . But for large n and m , it is difficult to decide the exact fractional domination number. Motivated by this, nearly sharp upper and lower bounds are given to the fractional domination number of grid graphs. Furthermore, upper and lower bounds on the fractional total domination number of strong direct product of graphs are given.
文摘A set <em>S ⊆ V (G)</em> is called a geodetic set if every vertex of <em>G</em> lies on a shortest <em>u-v</em> path for some <em>u, v ∈ S</em>, the minimum cardinality among all geodetic sets is called geodetic number and is denoted by <img src="Edit_82259359-0135-4a65-9378-b767f0405b48.png" alt="" />. A set <em>C ⊆ V (G)</em> is called a chromatic set if <em>C</em> contains all vertices of different colors in<em> G</em>, the minimum cardinality among all chromatic sets is called the chromatic number and is denoted by <img src="Edit_d849148d-5778-459b-abbb-ff25b5cd659b.png" alt="" />. A geo-chromatic set<em> S</em><sub><em>c</em></sub><em> ⊆ V (G</em><em>)</em> is both a geodetic set and a chromatic set. The geo-chromatic number <img src="Edit_505e203c-888c-471c-852d-4b9c2dd1a31c.png" alt="" /><em> </em>of<em> G</em> is the minimum cardinality among all geo-chromatic sets of<em> G</em>. In this paper, we determine the geodetic number and the geo-chromatic number of 2-cartesian product of some standard graphs like complete graphs, cycles and paths.
文摘A dominating set of a graph G is a set of vertices that contains at least one endpoint of every edge on the graph. The domination number of G is the order of a minimum dominating set of G. The (t, r) broadcast domination is a generalization of domination in which a set of broadcasting vertices emits signals of strength t that decrease by 1 as they traverse each edge, and we require that every vertex in the graph receives a cumulative signal of at least r from its set of broadcasting neighbors. In this paper, we extend the study of (t, r) broadcast domination to directed graphs. Our main result explores the interval of values obtained by considering the directed (t, r) broadcast domination numbers of all orientations of a graph G. In particular, we prove that in the cases r = 1 and (t, r) = (2, 2), for every integer value in this interval, there exists an orientation of G which has directed (t, r) broadcast domination number equal to that value. We also investigate directed (t, r) broadcast domination on the finite grid graph, the star graph, the infinite grid graph, and the infinite triangular lattice graph. We conclude with some directions for future study.
文摘对于“双高”电力系统的安全稳定运行而言,快速且准确的暂态功角稳定评估(transient angle stability assessment,TASA)方法至关重要。该文提出一种考虑并网变流器(grid side converter,GSC)切换控制特性且适用多新能源并网场景的TASA方法。首先,建立了“双高”电力系统的异质图模型(heterogenous information network model based on power system,HINPS),引入GSC二次侧控制参数构建HINPS中GSC节点的特征向量;然后,构建了异质时空神经网络(heterogenous spatial-temporal neural network,HSTN),其中图神经网络和循环神经网络的级联结构和差异化的节点特征聚合策略有效提高了模型的信息提取能力。IEEE-39节点和IEEE-300节点系统的实验结果表明,该方法可以准确评估系统的暂态功角稳定性,并表现出良好的泛化性能,具备在大规模电网中应用的潜力。
