Let be a graph with n vertices and m edges. The sum of absolute value of all coefficients of matching polynomial is called Hosoya index. In this paper, we determine 2<sup>nd</sup> to 4<sup>th</sup...Let be a graph with n vertices and m edges. The sum of absolute value of all coefficients of matching polynomial is called Hosoya index. In this paper, we determine 2<sup>nd</sup> to 4<sup>th</sup> minimum Hosoya index of a kind of tetracyclic graph, with m = n +3.展开更多
Let G be a （molecular） graph. The Hosoya index Z（G） of G is defined as the number of subsets of the edge set E（G） in which no two edges are adjacent in G, i.e., Z（G） is the total number of matchings of G. In t...Let G be a （molecular） graph. The Hosoya index Z（G） of G is defined as the number of subsets of the edge set E（G） in which no two edges are adjacent in G, i.e., Z（G） is the total number of matchings of G. In this paper, we determine all the connected graphs G with n ＋ 1 ≤ Z（G） ≤5n - 17 for n ≥ 19. As a byproduct, the graphs of n vertices with Hosoya index from the second smallest value to the twenty first smallest value are obtained for n ≥ 19.展开更多
The problem of subgraph matching is one fundamental issue in graph search,which is NP-Complete problem.Recently,subgraph matching has become a popular research topic in the field of knowledge graph analysis,which has ...The problem of subgraph matching is one fundamental issue in graph search,which is NP-Complete problem.Recently,subgraph matching has become a popular research topic in the field of knowledge graph analysis,which has a wide range of applications including question answering and semantic search.In this paper,we study the problem of subgraph matching on knowledge graph.Specifically,given a query graph q and a data graph G,the problem of subgraph matching is to conduct all possible subgraph isomorphic mappings of q on G.Knowledge graph is formed as a directed labeled multi-graph having multiple edges between a pair of vertices and it has more dense semantic and structural features than general graph.To accelerate subgraph matching on knowledge graph,we propose a novel subgraph matching algorithm based on subgraph index for knowledge graph,called as FGqT-Match.The subgraph matching algorithm consists of two key designs.One design is a subgraph index of matching-driven flow graph(FGqT),which reduces redundant calculations in advance.Another design is a multi-label weight matrix,which evaluates a near-optimal matching tree for minimizing the intermediate candidates.With the aid of these two key designs,all subgraph isomorphic mappings are quickly conducted only by traversing FGqj.Extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms.展开更多
A mixed graph G^(-) is obtained by orienting some edges of G, where G is the underlying graph of G^(-) . The positive inertia index, denoted by p~+( G), and the negative inertia index, denoted by n~-(G^(-) ), of a mix...A mixed graph G^(-) is obtained by orienting some edges of G, where G is the underlying graph of G^(-) . The positive inertia index, denoted by p~+( G), and the negative inertia index, denoted by n~-(G^(-) ), of a mixed graph G^(-) are the integers specifying the numbers of positive and negative eigenvalues of the Hermitian adjacent matrix of G^(-) , respectively. In this paper, the positive and negative inertia indices of the mixed unicyclic graphs are studied. Moreover, the upper and lower bounds of the positive and negative inertia indices of the mixed graphs are investigated, and the mixed graphs which attain the upper and lower bounds are characterized respectively.展开更多
The Hosoya index of a graph is defined as the total number of the matching of the graph. In this paper, the ordering of polygonal chains with respect to Hosoya index is characterized.
Chemical compounds are modeled as graphs.The atoms of molecules represent the graph vertices while chemical bonds between the atoms express the edges.The topological indices representing the molecular graph correspond...Chemical compounds are modeled as graphs.The atoms of molecules represent the graph vertices while chemical bonds between the atoms express the edges.The topological indices representing the molecular graph corresponds to the different chemical properties of compounds.Let a,b be are two positive integers,andΓ(Z_(a)×Z_(b))be the zero-divisor graph of the commutative ring Z_(a)×Z_(b).In this article some direct questions have been answered that can be utilized latterly in different applications.This study starts with simple computations,leading to a quite complex ring theoretic problems to prove certain properties.The theory of finite commutative rings is useful due to its different applications in the fields of advanced mechanics,communication theory,cryptography,combinatorics,algorithms analysis,and engineering.In this paper we determine the distance-based topological polynomials and indices of the zero-divisor graph of the commutative ring Z_(p^(2))×Z_(q)(for p,q as prime numbers)with the help of graphical structure analysis.The study outcomes help in understanding the fundamental relation between ring-theoretic and graph-theoretic properties of a zero-divisor graphΓ(G).展开更多
Let G be a simple graph. Define R(G) to be the graph obtained from G by adding a new vertex e* corresponding to each edge e = (a, b) of G and by joining each new vertex e* to the end vertices a and b of the edge e cor...Let G be a simple graph. Define R(G) to be the graph obtained from G by adding a new vertex e* corresponding to each edge e = (a, b) of G and by joining each new vertex e* to the end vertices a and b of the edge e corresponding to it. In this paper, we prove that the number of matchings of R(G) is completely determined by the degree sequence of vertices of G.展开更多
The Merrifield-Simmons index of a graph is defined as the total number of the independent sets of the graph and the Ho- soya index of a graph is defined as the total number of the match- ings of the graph. In this pap...The Merrifield-Simmons index of a graph is defined as the total number of the independent sets of the graph and the Ho- soya index of a graph is defined as the total number of the match- ings of the graph. In this paper, the definition of a class of po- lygonal chains is given, ordering of the polygonal chains with respect to Merrifield-Simmons index and Hosoya index are ob- tained, and their extremal graphs with respect to these two topo- logical indices are determined.展开更多
The Merrifield-Simmons index and Hosoya index are defined as the number of the graph G（V, E） as the number of subsets of V（G） in which no tow vertices are adjacent and the number of subsets of E（G） in which no t...The Merrifield-Simmons index and Hosoya index are defined as the number of the graph G（V, E） as the number of subsets of V（G） in which no tow vertices are adjacent and the number of subsets of E（G） in which no two edges are incident, respectively. In this paper, we characterize the Unicyclic graphs with Merrifield-Simmons indices and Hosoya indices, respectively. And double-cyclic graphs with Hosoya indices among the doublecyclic graphs with n vertices.展开更多
文摘Let be a graph with n vertices and m edges. The sum of absolute value of all coefficients of matching polynomial is called Hosoya index. In this paper, we determine 2<sup>nd</sup> to 4<sup>th</sup> minimum Hosoya index of a kind of tetracyclic graph, with m = n +3.
基金Supported by the National Natural Science Foundation of China(10761008, 10461009)the Science Foundation of the State Education Ministry of China(205170)
文摘Let G be a （molecular） graph. The Hosoya index Z（G） of G is defined as the number of subsets of the edge set E（G） in which no two edges are adjacent in G, i.e., Z（G） is the total number of matchings of G. In this paper, we determine all the connected graphs G with n ＋ 1 ≤ Z（G） ≤5n - 17 for n ≥ 19. As a byproduct, the graphs of n vertices with Hosoya index from the second smallest value to the twenty first smallest value are obtained for n ≥ 19.
基金the National Natural Science Foundation of China(Grant Nos.61976032,62002039).
文摘The problem of subgraph matching is one fundamental issue in graph search,which is NP-Complete problem.Recently,subgraph matching has become a popular research topic in the field of knowledge graph analysis,which has a wide range of applications including question answering and semantic search.In this paper,we study the problem of subgraph matching on knowledge graph.Specifically,given a query graph q and a data graph G,the problem of subgraph matching is to conduct all possible subgraph isomorphic mappings of q on G.Knowledge graph is formed as a directed labeled multi-graph having multiple edges between a pair of vertices and it has more dense semantic and structural features than general graph.To accelerate subgraph matching on knowledge graph,we propose a novel subgraph matching algorithm based on subgraph index for knowledge graph,called as FGqT-Match.The subgraph matching algorithm consists of two key designs.One design is a subgraph index of matching-driven flow graph(FGqT),which reduces redundant calculations in advance.Another design is a multi-label weight matrix,which evaluates a near-optimal matching tree for minimizing the intermediate candidates.With the aid of these two key designs,all subgraph isomorphic mappings are quickly conducted only by traversing FGqj.Extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms.
基金the National Natural Science Foundation of China (Nos. 11971054 and 12161141005)the Fundamental Research Funds for the Central Universities (No. 2016JBM071)。
文摘A mixed graph G^(-) is obtained by orienting some edges of G, where G is the underlying graph of G^(-) . The positive inertia index, denoted by p~+( G), and the negative inertia index, denoted by n~-(G^(-) ), of a mixed graph G^(-) are the integers specifying the numbers of positive and negative eigenvalues of the Hermitian adjacent matrix of G^(-) , respectively. In this paper, the positive and negative inertia indices of the mixed unicyclic graphs are studied. Moreover, the upper and lower bounds of the positive and negative inertia indices of the mixed graphs are investigated, and the mixed graphs which attain the upper and lower bounds are characterized respectively.
基金Supported by the National Natural Science Foundation of China(10761008)the Scientific Research Foundation of the Education Department of Guangxi Province of China(201010LX471,201010LX495,201106LX595,201106LX608)the Natural Science Fund of Hechi University(2011YBZ-N003,2012YBZ-N004)
文摘The Hosoya index of a graph is defined as the total number of the matching of the graph. In this paper, the ordering of polygonal chains with respect to Hosoya index is characterized.
文摘Chemical compounds are modeled as graphs.The atoms of molecules represent the graph vertices while chemical bonds between the atoms express the edges.The topological indices representing the molecular graph corresponds to the different chemical properties of compounds.Let a,b be are two positive integers,andΓ(Z_(a)×Z_(b))be the zero-divisor graph of the commutative ring Z_(a)×Z_(b).In this article some direct questions have been answered that can be utilized latterly in different applications.This study starts with simple computations,leading to a quite complex ring theoretic problems to prove certain properties.The theory of finite commutative rings is useful due to its different applications in the fields of advanced mechanics,communication theory,cryptography,combinatorics,algorithms analysis,and engineering.In this paper we determine the distance-based topological polynomials and indices of the zero-divisor graph of the commutative ring Z_(p^(2))×Z_(q)(for p,q as prime numbers)with the help of graphical structure analysis.The study outcomes help in understanding the fundamental relation between ring-theoretic and graph-theoretic properties of a zero-divisor graphΓ(G).
文摘Let G be a simple graph. Define R(G) to be the graph obtained from G by adding a new vertex e* corresponding to each edge e = (a, b) of G and by joining each new vertex e* to the end vertices a and b of the edge e corresponding to it. In this paper, we prove that the number of matchings of R(G) is completely determined by the degree sequence of vertices of G.
基金Supported by the National Natural Science Foundation of China(11161041)Innovative Team Subsidize of Northwest University for Nationalitiesthe Fundamental Research Funds for the Central Universities(31920140059)
文摘The Merrifield-Simmons index of a graph is defined as the total number of the independent sets of the graph and the Ho- soya index of a graph is defined as the total number of the match- ings of the graph. In this paper, the definition of a class of po- lygonal chains is given, ordering of the polygonal chains with respect to Merrifield-Simmons index and Hosoya index are ob- tained, and their extremal graphs with respect to these two topo- logical indices are determined.
基金This project is supported by National Natural Science Foundation of China（10671081） and the Science Foundation of Hubei Province（2006AA412C27）
文摘The Merrifield-Simmons index and Hosoya index are defined as the number of the graph G（V, E） as the number of subsets of V（G） in which no tow vertices are adjacent and the number of subsets of E（G） in which no two edges are incident, respectively. In this paper, we characterize the Unicyclic graphs with Merrifield-Simmons indices and Hosoya indices, respectively. And double-cyclic graphs with Hosoya indices among the doublecyclic graphs with n vertices.
