On the numbers of positive and negative eigenvalues of a graph.
A graph is a -graph, if one vertex has degree and the remaining vertices of have degree . In the special case of , the graph is -regular. Let and be integers such that and are of the same parity. If is a connected -graph of order without a matching of size , then we show in this paper the following: If , then and (i) . If is odd and an integer with , then (ii) for , (iii) for , (iv) for . If is even, then (v) for , (vi) for and , (vii) for...
H. Kheddouci, J.F. Saclé and M. Woźniak conjectured in 2000 that if a tree T is not a star, then there is an edge-disjoint placement of T into its third power.In this paper, we prove the conjecture for caterpillars.
Given a graph with colored edges, a Hamiltonian cycle is called alternating if its successive edges differ in color. The problem of finding such a cycle, even for 2-edge-colored graphs, is trivially NP-complete, while it is known to be polynomial for 2-edge-colored complete graphs. In this paper we study the parallel complexity of finding such a cycle, if any, in 2-edge-colored complete graphs. We give a new characterization for such a graph admitting an alternating Hamiltonian cycle which allows...
Let p be a positive integer and G = (V,E) a graph. A subset S of V is a p-dominating set if every vertex of V-S is dominated at least p times. The minimum cardinality of a p-dominating set a of G is the p-domination number γₚ(G). It is proved for a cactus graph G that γₚ(G) ⩽ (|V| + |Lₚ(G)| + c(G))/2, for every positive integer p ⩾ 2, where Lₚ(G) is the set of vertices of G of degree at most p-1 and c(G) is the number of odd cycles in G.
A partition of a positive integer n is a nonincreasing sequence of positive integers with sum Here we define a special class of partitions. 1. Let be a positive integer. Any partition of n whose Ferrers graph have no hook numbers divisible by t is known as a t- core partitionof The hooks are important in the representation theory of finite symmetric groups and the theory of cranks associated with Ramanujan’s congruences for the ordinary partition function [3,4,6]. If and , then we define...