On the critical ideals of graphs

We introduce some determinantal ideals of the generalized Laplacian matrix associated to a digraph G, that we call critical ideals of G. Critical ideals generalize the critical group and the characteristic polynomials of the adjacency and Laplacian matrices of a digraph. The main results of this article are the determination of some minimal generator sets and the reduced Gröbner basis for the critical ideals of the complete graphs, the cycles and the paths. Also, we establish a bound between the number of trivial critical ideals and the stability and clique numbers of a graph.     

On an open problem concerning total domination critical graphs

A graph G   with no isolated vertex is total domination vertex critical if for any vertex v$v$ of G   that is not adjacent to a vertex of degree one, the total domination number of G-v$G-v$ is less than the total domination number of G  . We call these graphs _γt${\gamma }_t$-critical. If such a graph G has total domination number k, we call it k  -_γt${\gamma }_t$-critical. We verify an open problem of k  -_γt${\gamma }_t$-critical graphs and obtain some results on the characterization of total domination critical graphs of order n=Δ(G)(_γt(G)-1)+1$n=\Delta (G)({\gamma }_t(G)-1)+1$.     

On the unimodality of independence polynomials of very well-covered graphs

The independence polynomial $i(G,x)$ of a graph $G$ is the generating function of the numbers of independent sets of each size. A graph of order $n$ is very well-covered if every maximal independent set has size $n∕2$. Levit and Mandrescu conjectured that the independence polynomial of every very well-covered graph is unimodal (that is, the sequence of coefficients is nondecreasing, then nonincreasing). In this article we show that every graph is embeddable as an induced subgraph of a very well-covered graph whose independence polynomial is unimodal, by considering the location of the roots of such polynomials.     

On minimum secure dominating sets of graphs

A subset X of the vertex set of a graph G is a secure dominating set of G if X is a dominating set of G and if, for each vertex u not in X, there is a neighbouring vertex v of u in X such that the swap set (X/{v}) ? {u} is again a dominating set of G, in which case v is called a defender. The secure domination number of G is the cardinality of a smallest secure dominating set of G. In this paper, we show that every graph of minimum degree at least 2 possesses a minimum secure dominating set in which all vertices are defenders. We also characterise the classes of graphs that have secure domination numbers 1, 2 and 3.     

On the spectral density function of the Laplacian of a graph

Let X$X$ be a finite graph. Let |V|$\left|V\right|$ be the number of its vertices and d$d$ be its degree. Denote by _F1(X)$F_1\left(X\right)$ its first spectral density function which counts the number of eigenvalues ≤λ²$\le {\lambda }^2$ of the associated Laplace operator. We provide an elementary proof for the estimate _F1(X)(λ)−_F1(X)(0)≤2⋅(|V|−1)⋅d⋅λ$F_1\left(X\right)\left(\lambda \right)-F_1\left(X\right)\left(0\right)\le 2\cdot (\left|V\right|-1)\cdot d\cdot \lambda$ for 0≤λ<1$0\le \lambda <1$ which has already been proved by Friedman (1996) [3] before. We explain how this gives evidence for conjectures about approximating Fuglede–Kadison determinants and L²$L^2$-torsion.     

On the topology of components of some Springer fibers and their relation to Kazhdan-Lusztig theory

We describe the irreducible components of Springer fibers for hook and two-row nilpotent elements of as iterated bundles of flag manifolds and Grassmannians. We then relate the topology (in particular, the intersection homology Poincaré polynomials) of the pairwise intersections of these components with the inner products of the Kazhdan-Lusztig basis elements of irreducible representations of the rational Iwahori-Hecke algebra of type A corresponding to the hook and two-row Young shapes.     

On a combinatorial property of choice functions of finite sets

We consider choice functions k[X]→X, where X is a finite set and k[X] denotes the set of all k-subsets of X. We define a property of domination for such maps generalizing the classical case k=2 (tournaments) and prove the existence of a dominating element generalizing the existence of a 2-root (king) in the classical case.     

On perturbations of almost distance-regular graphs

In this paper we show that certain almost distance-regular graphs, the so-called h-punctually walk-regular graphs, can be characterized through the cospectrality of their perturbed graphs. A graph G with diameter D is called h-punctually walk-regular, for a given h≤D, if the number of paths of length ? between a pair of vertices u,v at distance h depends only on ?. The graph perturbations considered here are deleting a vertex, adding a loop, adding a pendant edge, adding/removing an edge, amalgamating vertices, and adding a bridging vertex. We show that for walk-regular graphs some of these operations are equivalent, in the sense that one perturbation produces cospectral graphs if and only if the others do. Our study is based on the theory of graph perturbations developed by Cvetkovi?, Godsil, McKay, Rowlinson, Schwenk, and others. As a consequence, some new characterizations of distance-regular graphs are obtained.     

On combinatorial formulas for Macdonald polynomials

A recent breakthrough in the theory of (type A) Macdonald polynomials is due to Haglund, Haiman and Loehr, who exhibited a combinatorial formula for these polynomials in terms of a pair of statistics on fillings of Young diagrams. Ram and Yip gave a formula for the Macdonald polynomials of arbitrary type in terms of so-called alcove walks; these originate in the work of Gaussent-Littelmann and of the author with Postnikov on discrete counterparts to the Littelmann path model. In this paper, we relate the above developments, by explaining how the Ram-Yip formula compresses to a new formula, which is similar to the Haglund-Haiman-Loehr one but contains considerably fewer terms.     

On the lattice formed by all normal subloops of a finite loop

All normal subloops of a loopG form a modular latticeL _n (G). It is shown that a finite loopG has a complemented normal subloop lattice if and only ifG is a direct product of simple subloops. In particular,L _n (G) is a Boolean algebra if and only if no two isomorphic factors occurring in a decomposition ofG are abelian groups. The normal subloop lattice of a finite loop is a projective geometry if and only ifG is an elementary abelianp-group for some primep.     

On Riesz and Wishart distributions associated with decomposable undirected graphs

Classical Wishart distributions on the open convex cone of positive definite matrices and their fundamental features are extended to generalized Riesz and Wishart distributions associated with decomposable undirected graphs using the basic theory of exponential families. The families of these distributions are parameterized by their expectations/natural parameter and multivariate shape parameter and have a non-trivial overlap with the generalized Wishart distributions defined in Andersson and Wojnar (2004) [4] and [8]. This work also extends the Wishart distributions of type I in Letac and Massam (2007) [7] and, more importantly, presents an alternative point of view on the latter paper.     

Vertex decomposability and regularity of very well-covered graphs

A graph is called very well-covered if it is unmixed without isolated vertices such that the cardinality of each minimal vertex cover is half the number of vertices. We first prove that a very well-covered graph is Cohen-Macaulay if and only if it is vertex decomposable. Next, we show that the Castelnuovo-Mumford regularity of the quotient ring of the edge ideal of a very well-covered graph is equal to the maximum number of pairwise 3-disjoint edges.     

Optimal clustering of multipartite graphs

Given a graph G=(X,U), the problem dealt within this paper consists in partitioning X into a disjoint union of cliques by adding or removing a minimum number z(G) of edges (Zahn's problem). While the computation of z(G) is NP-hard in general, we show that its computation can be done in polynomial time when G is bipartite, by relating it to a maximum matching problem. When G is a complete multipartite graph, we give an explicit formula specifying z(G) with respect to some structural features of G. In both cases, we give also the structure of all the optimal clusterings of G.     

On graphs whose star sets are (co-)cliques

In this paper we study graphs all of whose star sets induce cliques or co-cliques. We show that the star sets of every tree for each eigenvalue are independent sets. Among other results it is shown that each star set of a connected graph G with three distinct eigenvalues induces a clique if and only if G=K_1,2 or K_2,…,2. It is also proved that stars are the only graphs with three distinct eigenvalues having a star partition with independent star sets.     

Parameterization of all solutions of the three chains completion problem

The family of all solutions of the three chains completion problem with a prescribed tolerance is described explicitly. It is shown that this family can be parameterized by a natural set of contractive upper triangular operators. As an application all solutions to a suboptimal nonstationary Nehari problem are described.     

Dominating sets of the comaximal and ideal-based zero-divisor graphs of commutative rings

Abstract

Let R be a commutative ring with nonzero identity, and let I be an ideal of R. The ideal-based zero-divisor graph of R, denoted by Γ_I (R), is the graph whose vertices are the set {x ∈ R \ I| xy ∈ I for some y∈ R \ I} and two distinct vertices x and y are adjacent if and only if xy ∈ I. Define the comaximal graph of R, denoted by CG(R), to be a graph whose vertices are the elements of R, where two distinct vertices a and b are adjacent if and only if Ra+Rb=R. A nonempty set S ? V of a graph G=(V, E) is a dominating set of G if every vertex in V is either in S or is adjacent to a vertex in S. The domination number γ(G) of G is the minimum cardinality among the dominating sets of G. The main object of this paper is to study the dominating sets and domination number of Γ_I (R) and the comaximal graph CG₂(R) \ J (R) (or CGJ (R) for short) where CG₂(R) is the subgraph of CG(R) induced on the nonunit elements of R and J (R) is the Jacobson radical of R.     

The colorings of homeomorphisms on connected graphs

In this paper, we decide the exact value of the color number of a fixed point free homeomorphism on a connected locally finite graph. We prove that for every fixed-point free homeomorphism from a connected locally finite graph into itself, the greatest common divisor of all period for its map is equal to one or three if and only if its color number is 4.     

Ratio asymptotic of Hermite-Padé orthogonal polynomials for Nikishin systems. II

We prove ratio asymptotic for sequences of multiple orthogonal polynomials with respect to a Nikishin system of measures N(σ₁,…,σm) such that for each k, σk has constant sign on its support consisting on an interval , on which almost everywhere, and a set without accumulation points in .