Spanning tree(τ)has an enormous application in computer science and chemistry to determine the geometric and dynamics analysis of compact polymers.In the field of medicines,it is helpful to recognize the epidemiology...Spanning tree(τ)has an enormous application in computer science and chemistry to determine the geometric and dynamics analysis of compact polymers.In the field of medicines,it is helpful to recognize the epidemiology of hepatitis C virus(HCV)infection.On the other hand,Kemeny’s constant(Ω)is a beneficial quantifier characterizing the universal average activities of a Markov chain.This network invariant infers the expressions of the expected number of time-steps required to trace a randomly selected terminus state since a fixed beginning state si.Levene and Loizou determined that the Kemeny’s constant can also be obtained through eigenvalues.Motivated by Levene and Loizou,we deduced the Kemeny’s constant and the number of spanning trees of hexagonal ring network by their normalized Laplacian eigenvalues and the coefficients of the characteristic polynomial.Based on the achieved results,entirely results are obtained for the M鯾ius hexagonal ring network.展开更多
Given a simple connected graph G, we consider two iterated constructions associated with G: Fk (G) and Rk (G) . In this paper, we completely obtain the normalized Laplacian spectrum of Fk (G) and Rk (G) , with k ≥2, ...Given a simple connected graph G, we consider two iterated constructions associated with G: Fk (G) and Rk (G) . In this paper, we completely obtain the normalized Laplacian spectrum of Fk (G) and Rk (G) , with k ≥2, respectively. As applications, we derive the closed-formula of the multiplicative degree-Kirchhoff index, the Kemeny’s constant, and the number of spanning trees of Fk?(G)? , Rk?(G) , r-iterative graph ,Frk?(G)? and r-iterative graph , where k?≥2 and r?≥1 . Our results extend those main results proposed by Pan et al. (2018), and we provide a method to characterize the normalized Laplacian spectrum of iteratively constructed complex graphs.展开更多
We analyze a common feature of p-Kemeny AGGregation（p-KAGG） and p-One-Sided Crossing Minimization（p-OSCM） to provide new insights and findings of interest to both the graph drawing community and the social choice ...We analyze a common feature of p-Kemeny AGGregation（p-KAGG） and p-One-Sided Crossing Minimization（p-OSCM） to provide new insights and findings of interest to both the graph drawing community and the social choice community. We obtain parameterized subexponential-time algorithms for p-KAGG—a problem in social choice theory—and for p-OSCM—a problem in graph drawing. These algorithms run in time O＊（2O（√k log k））,where k is the parameter, and significantly improve the previous best algorithms with running times O.1.403k/and O.1.4656k/, respectively. We also study natural ＂above-guarantee＂ versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of p-directed feedback arc set. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of ＂votes＂ in the input to p-KAGG is odd the above guarantee version can still be solved in time O＊（2O（√k log k））, while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails（equivalently, unless FPT D M[1]）.展开更多
文摘Spanning tree(τ)has an enormous application in computer science and chemistry to determine the geometric and dynamics analysis of compact polymers.In the field of medicines,it is helpful to recognize the epidemiology of hepatitis C virus(HCV)infection.On the other hand,Kemeny’s constant(Ω)is a beneficial quantifier characterizing the universal average activities of a Markov chain.This network invariant infers the expressions of the expected number of time-steps required to trace a randomly selected terminus state since a fixed beginning state si.Levene and Loizou determined that the Kemeny’s constant can also be obtained through eigenvalues.Motivated by Levene and Loizou,we deduced the Kemeny’s constant and the number of spanning trees of hexagonal ring network by their normalized Laplacian eigenvalues and the coefficients of the characteristic polynomial.Based on the achieved results,entirely results are obtained for the M鯾ius hexagonal ring network.
文摘Given a simple connected graph G, we consider two iterated constructions associated with G: Fk (G) and Rk (G) . In this paper, we completely obtain the normalized Laplacian spectrum of Fk (G) and Rk (G) , with k ≥2, respectively. As applications, we derive the closed-formula of the multiplicative degree-Kirchhoff index, the Kemeny’s constant, and the number of spanning trees of Fk?(G)? , Rk?(G) , r-iterative graph ,Frk?(G)? and r-iterative graph , where k?≥2 and r?≥1 . Our results extend those main results proposed by Pan et al. (2018), and we provide a method to characterize the normalized Laplacian spectrum of iteratively constructed complex graphs.
基金supported by a GermanNorwegian PPP grantsupported by the Indo-German Max Planck Center for Computer Science (IMPECS)
文摘We analyze a common feature of p-Kemeny AGGregation（p-KAGG） and p-One-Sided Crossing Minimization（p-OSCM） to provide new insights and findings of interest to both the graph drawing community and the social choice community. We obtain parameterized subexponential-time algorithms for p-KAGG—a problem in social choice theory—and for p-OSCM—a problem in graph drawing. These algorithms run in time O＊（2O（√k log k））,where k is the parameter, and significantly improve the previous best algorithms with running times O.1.403k/and O.1.4656k/, respectively. We also study natural ＂above-guarantee＂ versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of p-directed feedback arc set. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of ＂votes＂ in the input to p-KAGG is odd the above guarantee version can still be solved in time O＊（2O（√k log k））, while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails（equivalently, unless FPT D M[1]）.
