Characteristic polynomials of complement of graph bundles and their applications

We study the structure of the complement of an F-bundle over a graph G when it can be expressed as an F-bundle over another graph G. In particular, we compute the characteristie polynomial of the complement of an F-bundle when its voltages lie in and abelian subgroup Г of Aut(F) which acts freely and transitively on the vertices of the fiber F Some applications to regular embeddings of graph bundles into Euclidean spaces are also discussed     

Generalized characteristic polynomials of graph bundles

In this paper, we find computational formulae for generalized characteristic polynomials of graph bundles. We show that the number of spanning trees in a graph is the partial derivative (at (0,1)) of the generalized characteristic polynomial of the graph. Since the reciprocal of the Bartholdi zeta function of a graph can be derived from the generalized characteristic polynomial of a graph, consequently, the Bartholdi zeta function of a graph bundle can be computed by using our computational formulae.     

Several improved asymptotic normality criteria and their applications to graph polynomials

As widely regarded, one of the most classical and remarkable tools to measure the asymptotic normality of combinatorial statistics is due to Harper's real-rooted method proposed in 1967. However, this classical theorem exists some obvious shortcomings, for example, it requests all the roots of the corresponding generating function, which is impossible in general.Aiming to overcome this shortcoming in some extent, in this paper we present an improved asymptotic normality criterion, along with several variant versions, which usually just ask for one coefficient of the generating function, without knowing any roots. In virtue of these new criteria, the asymptotic normality of some usual combinatorial statistics can be revealed and extended. Among which, we introduce the applications to matching numbers and Laplacian coefficients in detail. Some relevant conjectures, proposed by Godsil (Combinatorica, 1981) and Wang et al. (J. Math. Anal. Appl., 2017), are generalized and verified as corollaries.     

Coloring graph bundles

Graph bundles generalize the notion of covering graphs and products of graphs. Several results about the chromatic numbers of graph bundles based on the Cartesian product, the strong product and the tensor product are presented. © 1995 John Wiley & Sons, Inc.     

On strong graph bundles

We study strong graph bundles : a concept imported from topology which generalizes both covering graphs and product graphs. Roughly speaking, a strong graph bundle always involves three graphs $E$, $B$ and $F$ and a projection $p:E\to B$ with fiber $F$ (i.e. $p^{?1}\left(x\right)?F$ for all $x\in V\left(B\right)$) such that the preimage of any edge $xy$ of $B$ is trivial (i.e. $p^{?1}\left(xy\right)?K_2?F$). Here we develop a framework to study which subgraphs $S$ of $B$ have trivial preimages (i.e. $p^{?1}\left(S\right)?S?F$) and this allows us to compare and classify several variations of the concept of strong graph bundle. As an application, we show that the clique operator preserves triangular graph bundles (strong graph bundles where preimages of triangles are trivial) thus yielding a new technique for the study of clique divergence of graphs.     

On weighted q-Daehee polynomials with their applications

In this paper, we first consider a generalization of Kim’s $p$-adic $q$-integral on ${\mathbb{Z}}_p$ including parameters $\alpha$ and $\beta$. By using this integral, we introduce the $q$-Daehee polynomials and numbers with weight $\left(\alpha ,\beta \right)$. Then, we obtain some interesting relationships and identities for these numbers and polynomials. We also derive some correlations among $q$-Daehee polynomials with weight $\left(\alpha ,\beta \right)$, $q$-Bernoulli polynomials with weight $\left(\alpha ,\beta \right)$ and Stirling numbers of second kind.     

Bipartitional polynomials and their applications in combinatorics and statistics

Bipartitional polynomials are multivariable polynomials Y_mn=Y_mn(cy₀₁,cy₁₀,cy₁₁,…,cy_mn), c^k≡c_k, defined by a sum over all partitions of the bipartite number (mn). Recurrence relations, generating functions and some basic properties of these polynomials are given. Applications in Combinatorics and Statistics are briefly indicated.     

Isoperimetric numbers of graph bundles

The main aim of this paper is to give some upper and lower bounds for the isoperimetric numbers of graph coverings or graph bundles, with exact values in some special cases. In addition, we show that the isoperimetric number of any covering graph is not greater than that of the base graph. Mohar's theorem for the isoperimetric number of the cartesian product of a graph and a complete graph can be extended to a more general case: The isoperimetric numberi(G × K _2n) of the cartesian product of any graphG and a complete graphK _2n on even vertices is the minimum of the isoperimetric numberi(G) andn, and it is also a sharp lower bound of the isoperimetric numbers of all graph bundles over the graphG with fiberK _2n. Furthermore, ifn 2i(G) then the isoperimetric number of any graph bundle overG with fibreK _n is equal to the isoperimetric numberi(G) ofG. Partially supported by The Ministry of Education, Korea.     

Mochizuki's indigenous bundles and Ehrhart polynomials

Mochizuki's work on torally indigenous bundles [1] yields combinatorial identities by degenerating to different curves of the same genus. We rephrase these identities in combinatorial language and strengthen them, giving relations between Ehrhart quasi-polynomials of different polytopes. We then apply the theory of Ehrhart quasi-polynomials to conclude that the number of dormant torally indigenous bundles on a general curve of a given type is expressed as a polynomial in the characteristic of the base field. In particular, we conclude the same for the number vector bundles of rank two and trivial determinant whose Frobenius-pullbacks are maximally unstable, as well as self-maps of the projective line with prescribed ramification. The second author was supported by a fellowship from the Japan Society for the Promotion of Science during the preparation of this paper.     

Wide diameter of Cartesian graph bundles

Fault tolerance and transmission delay of networks are important concepts in network design. The notions are strongly related to connectivity and diameter of a graph, and have been studied by many authors. Wide diameter of a graph combines studying connectivity with the diameter of a graph. Diameter with width k of a graph G, k-diameter, is defined as the minimum integer d for which there exist at least k internally disjoint paths of length at most d between any two distinct vertices in G. Denote by D_c(G) the c-diameter of G and κ(G) the connectivity of G. In the context of computer networks, wide diameters of Cartesian graph products have been recently studied by many authors. Cartesian graph bundles is a class of graphs that is a generalization of the Cartesian graph products. Let G be a Cartesian graph bundle with fiber F over base B, 0<a≤κ(F), and 0<b≤κ(B). We prove that D_a+b(G)≤D_a(F)+D_b(B)+1. Moreover, if G is a graph bundle with fiber F≠K₂ over base B≠K₂, then D_a+b(G)≤D_a(F)+D_b(B). The bounds are tight.     

On domination numbers of graph bundles

Letγ(G) be the domination number of a graphG. It is shown that for anyκ ≥ 0 there exists a Cartesian graph bundleB█φF such thatγ(B█φF) =γ(B)γ(F) — 2κ. The domination numbers of Cartesian bundles of two cycles are determined exactly when the fibre graph is a triangle or a square. A statement similar to Vizing’s conjecture on strong graph bundles is shown not to be true by proving the inequalityγ(B █ φF) ≤γ(B)γ(F) for strong graph bundles. Examples of graphsB andF withγ(B █ φF) γ(B)γ(F) are given.     

Fiber bundles with degenerations and their applications to computing fundamental groups

An analogue of the initial segment of the exact sequence of the homotopy groups of a fiber-bundle is written out for the map which is fiberbundle over some large subset of the base and has local sections over all points of the base. As an application, presentations of the fundamental groups of the complements of the arrangements of complexified reflection hyperplanes of the root systemsD _n andB _n in terms of generators and relations are computed.Research supported by Mrs Elizabeth and Mr Sydney Corob through the British Technion Society.     

Algorithm for recognizing Cartesian graph bundles

Graph bundles generalize the notion of covering graphs and graph products. In [8], authors constructed an algorithm that finds a presentation as a nontrivial Cartesian graph bundle for all graphs that are Cartesian graph bundles over triangle-free simple base. In [21], the unique square property is defined and it is shown that any equivalence relation possessing the unique square property determines the fundamental factorization of a graph as a nontrivial Cartesian graph bundle over arbitrary base graph. In this paper we define a relation Δ having a unique square property on Cartesian graph bundles over K₄e-free simple base. We also give a polynomial algorithm for recognizing Cartesian graph bundles over K₄e-free simple base.     

ARBORICITY AND COMPLEMENT OF A GRAPH

1.IntroductionAllthegraphsweconsiderareundirectedandsimple.ThecompletegraphofordernisdenotedbyKm,anindependentsetofnvenicesbyK..ThenotationGUHmeans*ThisresearchissupportedbytheNationalNaturalScienceFoundationofChina.thedisjointunionoftwographsGandH,andG HthedisjointunionofGandHplusalltheedgesbetweenGandH,HSGindicatesthatHisasubgraphofG.or(G)istheindependentnumberofG,0(G)thecardinalofthemaximumcliqueofG.ThearboricityofagraphGistheminimumnumberofsubsetsilltowhichtheedgesetofGcanbepar…     

Representation theorems for Tchebycheffian polynomials with boundary conditions and their applications

Representation theorems for Tchebycheff polynomials with homogeneous boundary conditions are proved, and a number of extremal problems are solved.     

Degenerate Bernoulli polynomials, generalized factorial sums, and their applications

We prove a general symmetric identity involving the degenerate Bernoulli polynomials and sums of generalized falling factorials, which unifies several known identities for Bernoulli and degenerate Bernoulli numbers and polynomials. We use this identity to describe some combinatorial relations between these polynomials and generalized factorial sums. As further applications we derive several identities, recurrences, and congruences involving the Bernoulli numbers, degenerate Bernoulli numbers, generalized factorial sums, Stirling numbers of the first kind, Bernoulli numbers of higher order, and Bernoulli numbers of the second kind.     

Theorems on partitioned matrices revisited and their applications to graph spectra

Some old results about spectra of partitioned matrices due to Goddard and Schneider or Haynsworth are re-proved. A new result is given for the spectrum of a block-stochastic matrix with the property that each off-diagonal block has equal entries and each diagonal block has equal diagonal entries and equal off-diagonal entries. The result is applied to the study of the spectra of the usual graph matrices by partitioning the vertex set of the graph according to the neighborhood equivalence relation. The concept of a reduced graph matrix is introduced. The question of when n-2 is the second largest signless Laplacian eigenvalue of a connected graph of order n is treated. A recent conjecture posed by Tam, Fan and Zhou on graphs that maximize the signless Laplacian spectral radius over all (not necessarily connected) graphs with given numbers of vertices and edges is refuted. The Laplacian spectrum of a (degree) maximal graph is reconsidered.