On the skew energy of orientations of hypercubes

Let D be a digraph of order n and λ₁,λ₂,…,λ_n denote all the eigenvalues of the skew-adjacency matrix of D. The skew energy E_S(D) of D is defined as . In this paper, it is proved that for any positive integer k≥3, there exists a k-regular graph of order n having an orientation D with . This work positively answers a problem proposed by Adiga et al. [C. Adiga, R. Balakrishnan, Wasin So, The skew energy of a digraph, Linear Algebra Appl. 432 (2010) 1825-1835]. In addition, a digraph is also constructed such that its skew energy is the same as the energy of its underlying graph.     

On a conjecture concerning the orientation number of a graph

For a connected graph G containing no bridges, let D(G) be the family of strong orientations of G; and for any D∈D(G), we denote by d(D) the diameter of D. The orientation number of G is defined by . Let G(p,q;m) denote the family of simple graphs obtained from the disjoint union of two complete graphs K_p and K_q by adding m edges linking them in an arbitrary manner. The study of the orientation numbers of graphs in G(p,q;m) was introduced by Koh and Ng [K.M. Koh, K.L. Ng, The orientation number of two complete graphs with linkages, Discrete Math. 295 (2005) 91-106]. Define and . In this paper we prove a conjecture on α proposed by K.M. Koh and K.L. Ng in the above mentioned paper, for q≥p+4.     

Directed defective asymmetric graph coloring games

We consider the following 2-person game which is played with an (initially uncolored) digraph D, a finite color set C, and nonnegative integers a, b, and d. Alternately, player I colors a vertices and player II colors b vertices with colors from C. Whenever a player colors a vertex v, all in-arcs (w,v) that do not come from a vertex w previously colored with the same color as v are deleted. For each color i the defect digraphD_i is the digraph induced by the vertices of color i at a certain state of the game. The main rule the players have to respect is that at every time for any color i the digraph D_i has maximum total degree of at most d. The game ends if no vertex can be colored any more according to this rule. Player I wins if D is completely colored at the end of the game, otherwise player II wins. The smallest cardinality of a color set C with which player I has a winning strategy for the game is called . This parameter generalizes several variants of Bodlaender’s game chromatic number. We determine the tight (resp., nearly tight) upper bound (resp., ) for the d-relaxed (a,b)-game chromatic number of orientations of forests (resp., undirected forests) for any d and a≥b≥1. Furthermore we prove that these numbers cannot be bounded in case a<b.     

Strong subtournaments containing a given vertex in regular multipartite tournaments

If x is a vertex of a digraph D, then we denote by d⁺(x) and d⁻(x) the outdegree and the indegree of x, respectively. The global irregularity of a digraph D is defined by

     

Generalized competition index of a primitive digraph

For positive integers k and m, and a digraph D, the k-step m-competition graph of D has the same set of vertices as D and an edge between vertices x and y if and only if there are distinct m vertices v₁,v₂,…,v_m in D such that there are directed walks of length k from x to v_i and from y to v_i for 1?i?m. In this paper, we present the definition of m-competition index for a primitive digraph. The m-competition index of a primitive digraph D is the smallest positive integer k such that is a complete graph. We study m-competition indices of primitive digraphs and provide an upper bound for the m-competition index of a primitive digraph.     

Longest cycles in almost regular 3-partite tournaments

If D is a digraph, then we denote by V(D) its vertex set. A multipartite or c-partite tournament is an orientation of a complete c-partite graph. The global irregularity of a digraph D is defined by

     

Generalization of transitive fraternal augmentations for directed graphs and its applications

Let be a directed graph. A transitive fraternal augmentation of is a directed graph with the same vertex set, including all the arcs of and such that for any vertices x,y,z,

1.

if and then or (fraternity);

2.

if and then (transitivity).

In this paper, we explore some generalization of the transitive fraternal augmentations for directed graphs and its applications. In particular, we show that the 2-coloring number col₂(G)≤O(∇₁(G)∇₀(G)²), where ∇_k(G) (k≥0) denotes the greatest reduced average density with depth k of a graph G; we give a constructive proof that ∇_k(G) bounds the distance (k+1)-coloring number col_k+1(G) with a function f(∇_k(G)). On the other hand, ∇_k(G)≤(col_2k+1(G))^2k+1. We also show that an inductive generalization of transitive fraternal augmentations can be used to study nonrepetitive colorings of graphs.     

Dimension-2 poset competition numbers and dimension-2 poset double competition numbers

Let D=(V(D),A(D)) be a digraph. The competition graph of D, is the graph with vertex set V(D) and edge set . The double competition graph of D, is the graph with vertex set V(D) and edge set . A poset of dimension at most two is a digraph whose vertices are some points in the Euclidean plane R² and there is an arc going from a vertex (x₁,y₁) to a vertex (x₂,y₂) if and only if x₁>x₂ and y₁>y₂. We show that a graph is the competition graph of a poset of dimension at most two if and only if it is an interval graph, at least half of whose maximal cliques are isolated vertices. This answers an open question on the doubly partial order competition number posed by Cho and Kim. We prove that the double competition graph of a poset of dimension at most two must be a trapezoid graph, generalizing a result of Kim, Kim, and Rho. Some connections are also established between the minimum numbers of isolated vertices required to be added to change a given graph into the competition graph, the double competition graph, of a poset and the minimum sizes of certain intersection representations of that graph.     

The vanishing order of certain Hecke L-functions of imaginary quadratic fields

Let −D<−4 denote a fundamental discriminant which is either odd or divisible by 8, so that the canonical Hecke character of exists. Let d be a fundamental discriminant prime to D. Let 2k−1 be an odd natural number prime to the class number of . Let χ be the twist of the (2k−1)th power of a canonical Hecke character of by the Kronecker's symbol . It is proved that the vanishing order of the Hecke L-function L(s,χ) at its central point s=k is determined by its root number when , where the constant implied in the symbol ? depends only on k and ?, and is effective for L-functions with root number −1.     

An upper bound on the domination number of a graph with minimum degree 2

A set S of vertices in a graph G is a dominating set of G if every vertex of V(G)?S is adjacent to some vertex in S. The minimum cardinality of a dominating set of G is the domination number of G, denoted as γ(G). Let P_n and C_n denote a path and a cycle, respectively, on n vertices. Let k₁(F) and k₂(F) denote the number of components of a graph F that are isomorphic to a graph in the family {P₃,P₄,P₅,C₅} and {P₁,P₂}, respectively. Let L be the set of vertices of G of degree more than 2, and let G−L be the graph obtained from G by deleting the vertices in L and all edges incident with L. McCuaig and Shepherd [W. McCuaig, B. Shepherd, Domination in graphs with minimum degree two, J. Graph Theory 13 (1989) 749-762] showed that if G is a connected graph of order n≥8 with δ(G)≥2, then γ(G)≤2n/5, while Reed [B.A. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996) 277-295] showed that if G is a graph of order n with δ(G)≥3, then γ(G)≤3n/8. As an application of Reed’s result, we show that if G is a graph of order n≥14 with δ(G)≥2, then .     

On hamiltonian colorings for some graphs

For a connected graph G and any two vertices u and v in G, let D(u,v) denote the length of a longest u-v path in G. A hamiltonian coloring of a connected graph G of order n is an assignment c of colors (positive integers) to the vertices of G such that |c(u)−c(v)|+D(u,v)≥n−1 for every two distinct vertices u and v in G. The value of a hamiltonian coloring c is the maximum color assigned to a vertex of G. The hamiltonian chromatic number of G is taken over all hamiltonian colorings c of G. In this paper we discuss the hamiltonian chromatic number of graphs G with . As examples, we determine the hamiltonian chromatic number for a class of caterpillars, and double stars.     

Combinatorial sums and finite differences

We present a new approach to evaluating combinatorial sums by using finite differences. Let and be sequences with the property that Δb_k=a_k for k?0. Let , and let . We derive expressions for g_n in terms of h_n and for h_n in terms of g_n. We then extend our approach to handle binomial sums of the form , , and , as well as sums involving unsigned and signed Stirling numbers of the first kind, and . For each type of sum we illustrate our methods by deriving an expression for the power sum, with a_k=k^m, and the harmonic number sum, with a_k=H_k=1+1/2+?+1/k. Then we generalize our approach to a class of numbers satisfying a particular type of recurrence relation. This class includes the binomial coefficients and the unsigned Stirling numbers of the first kind.     

Directed cyclic Hamiltonian cycle systems of the complete symmetric digraph

In this paper, we prove that directed cyclic Hamiltonian cycle systems of the complete symmetric digraph, , exist if and only if n is odd with n≠15 and n≠p^α for p an odd prime and α≥2 or with n≠2p^α for p an odd prime and α≥1. We also show that directed cyclic Hamiltonian cycle systems of the complete symmetric digraph minus a set of n/2 vertex-independent digons, (K_n−I)^∗, exist if and only if .     

Invariant hypersurfaces for derivations in positive characteristic

Let A be an integral k-algebra of finite type over an algebraically closed field k of characteristic p>0. Given a collection D of k-derivations on A, that we interpret as algebraic vector fields on , we study the group spanned by the hypersurfaces V(f) of X invariant under D modulo the rational first integrals of D. We prove that this group is always a finite dimensional F_p-vector space, and we give an estimate for its dimension. This is to be related to the results of Jouanolou and others on the number of hypersurfaces invariant under a foliation of codimension 1. As a application, given a k-algebra B between A^p and A, we show that the kernel of the pull-back morphism is a finite F_p-vector space. In particular, if A is a UFD, then the Picard group of B is finite.     

Coloring the Cartesian sum of graphs

For graphs G and H, let G⊕H denote their Cartesian sum. We investigate the chromatic number and the circular chromatic number for G⊕H. It has been proved that for any graphs G and H, . It has been conjectured that for any graphs G and H, . We confirm this conjecture for graphs G and H with special values of χ_c(G) and χ_c(H). These results improve previously known bounds on the corresponding coloring parameters for the Cartesian sum of graphs.     

A fast parallel algorithm for finding Hamiltonian cycles in dense graphs

Suppose that 0<η<1 is given. We call a graph, G, on n vertices an η-Chvátal graph if its degree sequence d₁≤d₂≤?≤d_n satisfies: for k<n/2, d_k≤min{k+ηn,n/2} implies d_n−k−ηn≥n−k. (Thus for η=0 we get the well-known Chvátal graphs.) An -algorithm is presented which accepts as input an η-Chvátal graph and produces a Hamiltonian cycle in G as an output. This is a significant improvement on the previous best -algorithm for the problem, which finds a Hamiltonian cycle only in Dirac graphs (δ(G)≥n/2 where δ(G) is the minimum degree in G).