Total domination in claw-free graphs with minimum degree 2

A set S of vertices in a graph G is a total dominating set (TDS) of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a TDS of G is the total domination number of G, denoted by γ_t(G). A graph is claw-free if it does not contain K_1,3 as an induced subgraph. It is known [M.A. Henning, Graphs with large total domination number, J. Graph Theory 35(1) (2000) 21-45] that if G is a connected graph of order n with minimum degree at least two and G∉{C₃,C₅, C₆, C₁₀}, then γ_t(G)?4n/7. In this paper, we show that this upper bound can be improved if G is restricted to be a claw-free graph. We show that every connected claw-free graph G of order n and minimum degree at least two satisfies γ_t(G)?(n+2)/2 and we characterize those graphs for which γ_t(G)=⌊(n+2)/2⌋.     

Bounds on total domination in claw-free cubic graphs

A set S of vertices in a graph G is a total dominating set, denoted by TDS, of G if every vertex of G is adjacent to some vertex in S (other than itself). The minimum cardinality of a TDS of G is the total domination number of G, denoted by γ_t(G). If G does not contain K_1,3 as an induced subgraph, then G is said to be claw-free. It is shown in [D. Archdeacon, J. Ellis-Monaghan, D. Fischer, D. Froncek, P.C.B. Lam, S. Seager, B. Wei, R. Yuster, Some remarks on domination, J. Graph Theory 46 (2004) 207-210.] that if G is a graph of order n with minimum degree at least three, then γ_t(G)?n/2. Two infinite families of connected cubic graphs with total domination number one-half their orders are constructed in [O. Favaron, M.A. Henning, C.M. Mynhardt, J. Puech, Total domination in graphs with minimum degree three, J. Graph Theory 34(1) (2000) 9-19.] which shows that this bound of n/2 is sharp. However, every graph in these two families, except for K₄ and a cubic graph of order eight, contains a claw. It is therefore a natural question to ask whether this upper bound of n/2 can be improved if we restrict G to be a connected cubic claw-free graph of order at least 10. In this paper, we answer this question in the affirmative. We prove that if G is a connected claw-free cubic graph of order n?10, then γ_t(G)?5n/11.     

A Greedy Partition Lemma for directed domination

A directed dominating set in a directed graph D is a set S of vertices of V such that every vertex u∈V(D)?S has an adjacent vertex v in S with v directed to u. The directed domination number of D, denoted by γ(D), is the minimum cardinality of a directed dominating set in D. The directed domination number of a graph G, denoted Γ_d(G), is the maximum directed domination number γ(D) over all orientations D of G. The directed domination number of a complete graph was first studied by Erd?s [P. Erd?s On a problem in graph theory, Math. Gaz. 47 (1963) 220–222], albeit in a disguised form. In this paper we prove a Greedy Partition Lemma for directed domination in oriented graphs. Applying this lemma, we obtain bounds on the directed domination number. In particular, if α denotes the independence number of a graph G, we show that α≤Γ_d(G)≤α(1+2ln(n/α)).     

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.     

The diameter of total domination vertex critical graphs

A graph G with no isolated vertex is total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G-v is less than the total domination number of G. These graphs we call γ_t-critical. If such a graph G has total domination number k, we call it k-γ_t-critical. We characterize the connected graphs with minimum degree one that are γ_t-critical and we obtain sharp bounds on their maximum diameter. We calculate the maximum diameter of a k-γ_t-critical graph for k?8 and provide an example which shows that the maximum diameter is in general at least 5k/3-O(1).     

On a conjecture of Murty and Simon on diameter 2-critical graphs

A graph G is diameter 2-critical if its diameter is two, and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter 2-critical graph of order n is at most n²/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. We use an association with total domination to prove the conjecture for the graphs whose complements have diameter three.     

Rank 2 stable vector bundles on Fano 3-folds of index 2

Let X be a Fano 3-fold of the first kind with index 2. In this paper, we characterize the chern classes of rank 2 stable vector bundles on X and we find a bound for the least twist of a rank 2 reflexive sheaf on X which has a global section.     

The proof on the conjecture of extremal graphs for the kth eigenvalues of trees

We consider the only remaining unsolved case n≡0 (mod k) for the largest kth eigenvalue λ_k.of trees with n vertices. In this paper, the conjecture for this problem in [Shao Jia-yu, On the largest kth eignevalues of trees, Linear Algebra Appl. 221 (1995) 131] is proved and (from this) the complete solution to this problem, the best upper bound and the extremal trees of λ_k, is given in general cases above.     

All graphs with maximum degree three whose complements have 4-cycle decompositions

Let G be the set that contains precisely the graphs on n vertices with maximum degree 3 for which there exists a 4-cycle system of their complement in K_n. In this paper G is completely characterized.     

On the 2-rainbow domination in graphs

The concept of 2-rainbow domination of a graph G coincides with the ordinary domination of the prism G□K₂. In this paper, we show that the problem of deciding if a graph has a 2-rainbow dominating function of a given weight is NP-complete even when restricted to bipartite graphs or chordal graphs. Exact values of 2-rainbow domination numbers of several classes of graphs are found, and it is shown that for the generalized Petersen graphs GP(n,k) this number is between ⌈4n/5⌉ and n with both bounds being sharp.     

The edge density of 4-critical planar graphs

Several constructions of 4-critical planar graphs are given. These provide answers to two questions of B. Grünbaum and give improved bounds for the maximum edge density of such graphs.     

Integrability of a nuclear spin generator

In this work we consider a nuclear spin generator given by where α, β, κ are nonnegative parameters. It models the two temperature feedback nuclear reactor problem as model by Vreeke and Sandquist (1970) [4]. We contribute to the understanding of its global dynamics, or more precisely, to the topological structure of its orbits by studying the integrability problem. We prove that β=0 or β≠0 and κ=0 are the only values of the parameters for which the system is integrable, and in this case we provide an explicit expression for its first integrals.     

A proof of Coleman's conjecture

Almost thirty years ago Coleman made a conjecture that for any convex lattice polygon with v vertices, g (g?1) interior lattice points and b boundary lattice points we have b?2g-v+10. In this note we give a proof of the conjecture. We also aim to describe all convex lattice polygons for which the bound b=2g-v+10 is attained.     

Motivic zeta functions of abelian varieties, and the monodromy conjecture

We prove for abelian varieties a global form of Denef and Loeser?s motivic monodromy conjecture, in arbitrary characteristic. More precisely, we prove that for every tamely ramified abelian variety A over a complete discretely valued field with algebraically closed residue field, its motivic zeta function has a unique pole at Chai?s base change conductor c(A) of A, and that the order of this pole equals one plus the potential toric rank of A. Moreover, we show that for every embedding of Q? in C, the value exp(2πic(A)) is an ?-adic tame monodromy eigenvalue of A. The main tool in the paper is Edixhoven?s filtration on the special fiber of the Néron model of A, which measures the behavior of the Néron model under tame base change.     

Discrete complex analysis on isoradial graphs

We study discrete complex analysis and potential theory on a large family of planar graphs, the so-called isoradial ones. Along with discrete analogues of several classical results, we prove uniform convergence of discrete harmonic measures, Green?s functions and Poisson kernels to their continuous counterparts. Among other applications, the results can be used to establish universality of the critical Ising and other lattice models.     

A simple proof of the Grobman–Hartman theorem for nonuniformly hyperbolic flows

We give a simple and direct proof of the Grobman–Hartman theorem for nonautonomous differential equations obtained from perturbing a nonuniform exponential dichotomy. In particular, we do not need to pass through discrete time and obtain the result as a consequence of a corresponding result for maps. To the best of our knowledge, this is the first direct approach for nonuniform exponential dichotomies. We also show that the conjugacies are continuous in time and Hölder continuous in space. In addition, we describe the dependence of the conjugacies on the perturbation, and we obtain a reversibility result for the conjugacies of reversible differential equations. We emphasize that the additional work required to consider nonuniform exponential dichotomies is substantial.     

The algebraic structure of relative twisted vertex operators

Twisted vertex operators based on rational lattices have had many applications in vertex operator algebra theory and conformal field theory. In this paper, “relativized” twisted vertex operators are constructed in a general context based on isometries of rational lattices, and a generalized twisted Jacobi identity is established for them. This result generalizes many previous results. Relatived untwisted vertex operators had been studied in a monograph by the authors. The present paper includes as a special case the proof of the main relations among twisted vertex operators based on even lattices announced some time ago by the second author.     

Distance paired domination numbers of graphs

In this paper, we study a generalization of the paired domination number. Let G=(V,E) be a graph without an isolated vertex. A set D⊆V(G) is a k-distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The k-distance paired domination number is the cardinality of a smallest k-distance paired dominating set of G. We investigate properties of the k-distance paired domination number of a graph. We also give an upper bound and a lower bound on the k-distance paired domination number of a non-trivial tree T in terms of the size of T and the number of leaves in T and we also characterize the extremal trees.     

On duality and fractionality of multicommodity flows in directed networks

In this paper we address a topological approach to multiflow (multicommodity flow) problems in directed networks. Given a terminal weight μ, we define a metrized polyhedral complex, called the directed tight span T_μ, and prove that the dual of the μ-weighted maximum multiflow problem reduces to a facility location problem on T_μ. Also, in case where the network is Eulerian, it further reduces to a facility location problem on the tropical polytope spanned by μ. By utilizing this duality, we establish the classifications of terminal weights admitting a combinatorial min–max relation (i) for every network and (ii) for every Eulerian network. Our result includes the Lomonosov–Frank theorem for directed free multiflows and Ibaraki–Karzanov–Nagamochi’s directed multiflow locking theorem as special cases.