Graphs with small diameter determined by their <Emphasis Type="Italic">D</Emphasis>-spectra

Let G be a connected graph with vertex set V(G) = {v₁, v₂,..., v _n }. The distance matrix D(G) = (d _ij )_n×n is the matrix indexed by the vertices of G, where d _ij denotes the distance between the vertices v _i and v _j . Suppose that λ₁(D) ≥ λ₂(D) ≥... ≥ λ _n (D) are the distance spectrum of G. The graph G is said to be determined by its D-spectrum if with respect to the distance matrix D(G), any graph having the same spectrum as G is isomorphic to G. We give the distance characteristic polynomial of some graphs with small diameter, and also prove that these graphs are determined by their D-spectra.     

Neighborhood contraction in graphs

Let G be a graph and v be any vertex of G. Then the neighborhood contracted graphG_v of G, with respect to the vertex v, is the graph with vertex set V ? N(v), where two vertices u,w ∈ V ? N(v) are adjacent in G_v if either w = v and u is adjacent to any vertex of N(v) in G or u,w ? N[v] and u,w are adjacent in G. The properties of the neighborhood contracted graphs are discussed in this paper. The neighborhood contraction in some special class of graphs, the domination in a graph and the neighborhood contracted graphs are discussed in the paper.     

Bivariate Binomial Moments and Bonferroni-Type Inequalities

We obtain bivariate forms of Gumbel’s, Fréchet’s and Chung’s linear inequalities for P(S ≥ u, T ≥ v) in terms of the bivariate binomial moments {S _{i, j} }, 1 ≤ i ≤ k,1 ≤ j ≤ l of the joint distribution of (S, T). At u = v = 1, the Gumbel and Fréchet bounds improve monotonically with non-decreasing (k, l). The method of proof uses combinatorial identities, and reveals a multiplicative structure before taking expectation over sample points.     

Some results on the annihilator graph of a commutative ring

Let R be a commutative ring. The annihilator graph of R, denoted by AG(R), is the undirected graph with all nonzero zero-divisors of R as vertex set, and two distinct vertices x and y are adjacent if and only if ann _R (xy) ≠ ann _R (x) ∪ ann _R (y), where for z ∈ R, ann _R (z) = {r ∈ R: rz = 0}. In this paper, we characterize all finite commutative rings R with planar or outerplanar or ring-graph annihilator graphs. We characterize all finite commutative rings R whose annihilator graphs have clique number 1, 2 or 3. Also, we investigate some properties of the annihilator graph under the extension of R to polynomial rings and rings of fractions. For instance, we show that the graphs AG(R) and AG(T(R)) are isomorphic, where T(R) is the total quotient ring of R. Moreover, we investigate some properties of the annihilator graph of the ring of integers modulo n, where n ? 1.     

Homological Epimorphisms, Compactly Generated t-Structures and Gorenstein-Projective Modules

The aim of this paper is two-fold. Given a recollement (T′, T, T″, i*, i_*, i^!, j_!, j*, j_*), where T′, T, T″ are triangulated categories with small coproducts and T is compactly generated. First, the authors show that the BBD-induction of compactly generated t-structures is compactly generated when i_* preserves compact objects. As a con-sequence, given a ladder (T′, T, T″, T, T′) of height 2, then the certain BBD-induction of compactly generated t-structures is compactly generated. The authors apply them to the recollements induced by homological ring epimorphisms. This is the first part of their work. Given a recollement (D(B-Mod),D(A-Mod),D(C-Mod), i*, i_*, i^!, j_!, j*, j_*) induced by a homological ring epimorphism, the last aim of this work is to show that if A is Gorenstein, _A B has finite projective dimension and j_! restricts to D ^b (C-mod), then this recollement induces an unbounded ladder (B-Gproj,A-Gproj, C-Gproj) of stable categories of finitely generated Gorenstein-projective modules. Some examples are described.     

Generalized 3-edge-connectivity of Cartesian product graphs

The generalized k-connectivity κ _k (G) of a graph G was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized k-edge-connectivity which is defined as λ _k (G) = min{λ(S): S ? V (G) and |S| = k}, where λ(S) denotes the maximum number l of pairwise edge-disjoint trees T ₁, T ₂, …, T _l in G such that S ? V (T _i ) for 1 ? i ? l. In this paper we prove that for any two connected graphs G and H we have λ ₃(G □ H) ? λ ₃(G) + λ ₃(H), where G □ H is the Cartesian product of G and H. Moreover, the bound is sharp. We also obtain the precise values for the generalized 3-edge-connectivity of the Cartesian product of some special graph classes.     

A Probabilistic Characterization of the Dominance Order on Partitions

We present a probabilistic characterization of the dominance order on partitions. Let ν be a partition and Y _ν its Ferrers diagram, i.e. a stack of rows of cells with row i containing ν _i cells. Let the cells of Y _ν be filled with independent and identically distributed draws from the random variable X = B i n(r, p) with r ≥ 1 and p ∈ (0, 1). Given j, t ≥ 0, let P(ν, j, t) be the probability that the sum of all the entries in Y _ν is j while the sum of the entries in each row of Y _ν is no more than t. It is shown that if ν and μ are two partitions of n, ν dominates μ if and only if P(ν, j, t) ≤ P(μ, j, t) for all j, t ≥ 0. It is shown that the same result holds if X is any log-concave integer valued random variable with {i : P(X = i) > 0} = {0, 1,…,r} for some r ≥ 1.     

On DP-coloring of graphs and multigraphs

While solving a question on the list coloring of planar graphs, Dvo?ák and Postle introduced the new notion of DP-coloring (they called it correspondence coloring). A DP-coloring of a graph G reduces the problem of finding a coloring of G from a given list L to the problem of finding a “large” independent set in the auxiliary graph H(G,L) with vertex set {(v, c): v ∈ V (G) and c ∈ L(v)}. It is similar to the old reduction by Plesnevi? and Vizing of the k-coloring problem to the problem of finding an independent set of size |V(G)| in the Cartesian product G□K _k, but DP-coloring seems more promising and useful than the Plesnevi?–Vizing reduction. Some properties of the DP-chromatic number χ _DP (G) resemble the properties of the list chromatic number χ _l (G) but some differ quite a lot. It is always the case that χ _DP (G) ≥ χ _l (G). The goal of this note is to introduce DP-colorings for multigraphs and to prove for them an analog of the result of Borodin and Erd?s–Rubin–Taylor characterizing the multigraphs that do not admit DP-colorings from some DP-degree-lists. This characterization yields an analog of Gallai’s Theorem on the minimum number of edges in n-vertex graphs critical with respect to DP-coloring.     

Lower bounds on the signed total k-domination number of graphs

Let G be a graph with vertex set V(G). For any integer k ≥ 1, a signed total k-dominating function is a function f: V(G) → {?1, 1} satisfying ∑_x∈N(v)f(x) ≥ k for every v ∈ V(G), where N(v) is the neighborhood of v. The minimum of the values ∑_v∈V(G)f(v), taken over all signed total k-dominating functions f, is called the signed total k-domination number. In this note we present some new sharp lower bounds on the signed total k-domination number of a graph. Some of our results improve known bounds.     

Conjugacy classes in Möbius groups

Let \({\mathbb H^{n+1}}\) denote the n + 1-dimensional (real) hyperbolic space. Let \({\mathbb {S}^{n}}\) denote the conformal boundary of the hyperbolic space. The group of conformal diffeomorphisms of \({\mathbb {S}^{n}}\) is denoted by M(n). Let M _o (n) be its identity component which consists of all orientation-preserving elements in M(n). The conjugacy classification of isometries in M _o (n) depends on the conjugacy of T and T ^?1 in M _o (n). For an element T in M(n), T and T ^?1 are conjugate in M(n), but they may not be conjugate in M _o (n). In the literature, T is called real if T is conjugate in M _o (n) to T ^?1. In this paper we classify real elements in M _o (n). Let T be an element in M _o (n). Corresponding to T there is an associated element T _o in SO(n + 1). If the complex conjugate eigenvalues of T _o are given by \({\{e^{i\theta_j}, e^{-i\theta_j}\}, 0 < \theta_j \leq \pi, j=1,\ldots,k}\) , then {θ₁, . . . , θ _k } are called the rotation angles of T. If the rotation angles of T are distinct from each-other, then T is called a regular element. After classifying the real elements in M _o (n) we have parametrized the conjugacy classes of regular elements in M _o (n). In the parametrization, when T is not conjugate to T ^?1 , we have enlarged the group and have considered the conjugacy class of T in M(n). We prove that each such conjugacy class can be induced with a fibration structure.     

An improvement of the five halves theorem of J. Boardman

Let (M ^m , T) be a smooth involution on a closed smooth m-dimensional manifold and F = ∪ _j=0 ⁿ F ^j (n ≤ m) its fixed point set, where F ^j denotes the union of those components of F having dimension j. The famous Five Halves Theorem of J. Boardman, announced in 1967, establishes that, if F is nonbounding, then m ≤ 5/2n. In this paper we obtain an improvement of the Five Halves Theorem when the top dimensional component of F, F ⁿ , is nonbounding. Specifically, let ω = (i ₁, i ₂, …, i _r ) be a non-dyadic partition of n and s _ω (x ₁, x ₂, …, x _n ) the smallest symmetric polynomial over Z ₂ on degree one variables x ₁, x ₂, …, x _n containing the monomial \(x_1^{i_1 } x_2^{i_2 } \cdots x_r^{i_r }\). Write s _ω (F ⁿ ) ∈ H ⁿ (F ⁿ , Z ₂) for the usual cohomology class corresponding to s _ω (x ₁, x ₂, …, x _n ), and denote by ?(F ⁿ ) the minimum length of a nondyadic partition ω with s _ω (F ⁿ ) ≠ 0 (here, the length of ω = (i ₁, i ₂, …, i _r ) is r). We will prove that, if (M ^m , T) is an involution for which the top dimensional component of the fixed point set, F ⁿ , is nonbounding, then m ≤ 2n + ?(F ⁿ ); roughly speaking, the bound for m depends on the degree of decomposability of the top dimensional component of the fixed point set. Further, we will give examples to show that this bound is best possible.     

On a generalization of the Hadwiger–Nelson problem

For a field F and a quadratic form Q defined on an n-dimensional vector space V over F, let QG _Q , called the quadratic graph associated to Q, be the graph with the vertex set V where vertices u,w ∈ V form an edge if and only if Q(v ? w) = 1. Quadratic graphs can be viewed as natural generalizations of the unit-distance graph featuring in the famous Hadwiger–Nelson problem. In the present paper, we will prove that for a local field F of characteristic zero, the Borel chromatic number of QG _Q is infinite if and only if Q represents zero non-trivially over F. The proof employs a recent spectral bound for the Borel chromatic number of Cayley graphs, combined with an analysis of certain oscillatory integrals over local fields. As an application, we will also answer a variant of question 525 proposed in the 22nd British Combinatorics Conference 2009 [6].     

On a classical theorem on the diameter and minimum degree of a graph

In this work, we obtain good upper bounds for the diameter of any graph in terms of its minimum degree and its order, improving a classical theorem due to Erd¨os, Pach, Pollack and Tuza.We use these bounds in order to study hyperbolic graphs(in the Gromov sense). To compute the hyperbolicity constant is an almost intractable problem, thus it is natural to try to bound it in terms of some parameters of the graph. Let H(n, δ_0) be the set of graphs G with n vertices and minimum degree δ_0, and J(n, Δ) be the set of graphs G with n vertices and maximum degree Δ. We study the four following extremal problems on graphs: a(n, δ_0) = min{δ(G) | G ∈ H(n, δ_0)}, b(n, δ_0) = max{δ(G) |G ∈ H(n, δ_0)}, α(n, Δ) = min{δ(G) | G ∈ J(n, Δ)} and β(n, Δ) = max{δ(G) | G ∈ J(n, Δ)}. In particular, we obtain bounds for b(n, δ_0) and we compute the precise value of a(n, δ_0), α(n, Δ) andβ(n, Δ) for all values of n, δ_0 and Δ, respectively.     

<Emphasis Type="Italic">r</Emphasis>-Dynamic Chromatic Number of Some Line Graphs

An r-dynamic coloring of a graph G is a proper coloring c of the vertices such that |c(N(v))| ≥ min {r, deg(v)}, for each v ∈ V (G). The r-dynamic chromatic number of a graph G is the smallest k such that G admits an r-dynamic coloring with k colors. In this paper, we obtain the r-dynamic chromatic number of the line graph of helm graphs H_n for all r between minimum and maximum degree of H_n. Moreover, our proofs are constructive, what means that we give also polynomial time algorithms for the appropriate coloring. Finally, as the first, we define an equivalent model for edge coloring.     

Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths

In 1982 Thomassen asked whether there exists an integer f(k,t) such that every strongly f(k,t)-connected tournament T admits a partition of its vertex set into t vertex classes V ₁,…V _t such that for all i the subtournament T[V _i] induced on T by V _i is strongly k-connected. Our main result implies an affirmative answer to this question. In particular we show that f(k, t)=O(k ⁷ t ⁴) suffices. As another application of our main result we give an affirmative answer to a question of Song as to whether, for any integer t, there exists aninteger h(t) such that every strongly h(t)-connected tournament has a 1-factor consisting of t vertex-disjoint cycles of prescribed lengths. We show that h(t)=O(t ⁵) suffices.     

(3, 1)*-Choosability of graphs of nonnegative characteristic without intersecting short cycles

A graph G is called (k,d)^?-choosable if for every list assignment L satisfying ∣L(v)∣ ≥k for all v∈V(G), there is an L-coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself. In this paper, it is proved that every graph of nonnegative characteristic without intersecting i-cycles for all i=3,4,5 is (3,1)^?-choosable.     

On Excess-time Correlated Cumulative Processes

In this paper a class of correlated cumulative processes, B _s (t) = ∑^N(t)_i=1 H _s (X _i )X _i , is studied with excess level increments X _i ?s, where {N(t), t ?0} is the counting process generated by the renewal sequence T _n , T _n and X _n are correlated for given n, H _s (t) is the Heaviside function and s?0 is a given constant. Several useful results, for the distributions of B _s (t), and that of the number of excess (non-excess) increments on (0, t) and the corresponding means, are derived. First passage time problems are also discussed and various asymptotic properties of the processes are obtained. Transform results, by applying a flexible form for the joint distribution of correlated pairs (T _n , X _n ) are derived and inverted. The case of non-excess level increments, X _i < s, is also considered. Finally, applications to known stochastic shock and pro-rata warranty models are given.     

On <Emphasis Type="Italic">g</Emphasis><Subscript><Emphasis Type="Italic">c</Emphasis></Subscript>-colorings of nearly bipartite graphs

Let G be a simple graph, let d(v) denote the degree of a vertex v and let g be a nonnegative integer function on V (G) with 0 ≤ g(v) ≤ d(v) for each vertex v ∈ V (G). A g _c -coloring of G is an edge coloring such that for each vertex v ∈ V (G) and each color c, there are at least g(v) edges colored c incident with v. The g _c -chromatic index of G, denoted by χ′g _c (G), is the maximum number of colors such that a gc-coloring of G exists. Any simple graph G has the g _c -chromatic index equal to δ _g (G) or δ _g (G) ? 1, where \({\delta _g}\left( G \right) = \mathop {\min }\limits_{v \in V\left( G \right)} \left\lfloor {d\left( v \right)/g\left( v \right)} \right\rfloor \). A graph G is nearly bipartite, if G is not bipartite, but there is a vertex u ∈ V (G) such that G ? u is a bipartite graph. We give some new sufficient conditions for a nearly bipartite graph G to have χ′g _c (G) = δ _g (G). Our results generalize some previous results due to Wang et al. in 2006 and Li and Liu in 2011.     

On infinite-rank singular perturbations of the Schrödinger operator

Schrödinger operators with infinite-rank singular potentials V=Σ _i,j=1 ^∞ b _ij〈φ_j,·〉φ_i are studied under the condition that the singular elements ψ _j are ξ _j(t)-invariant with respect to scaling transformationsin ?³.     

A note on the independent domination number versus the domination number in bipartite graphs

Let γ(G) and i(G) be the domination number and the independent domination number of G, respectively. Rad and Volkmann posted a conjecture that i(G)/γ(G) ≤ Δ(G)/2 for any graph G, where Δ(G) is its maximum degree (see N. J. Rad, L. Volkmann (2013)). In this work, we verify the conjecture for bipartite graphs. Several graph classes attaining the extremal bound and graphs containing odd cycles with the ratio larger than Δ(G)/2 are provided as well.