The Laplacian spectral radius of some bipartite graphs

In this paper, we study the largest Laplacian spectral radius of the bipartite graphs with n vertices and k cut edges and the bicyclic bipartite graphs, respectively. Identifying the center of a star K_1,k and one vertex of degree n of K_m,n, we denote by the resulting graph. We show that the graph (1?k?n-4) is the unique graph with the largest Laplacian spectral radius among the bipartite graphs with n vertices and k cut edges, and (n?7) is the unique graph with the largest Laplacian spectral radius among all the bicyclic bipartite graphs.     

Roman domination in regular graphs

A Roman domination function on a graph G=(V(G),E(G)) is a function f:V(G)→{0,1,2} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. The weight of a Roman dominating function is the value f(V(G))=∑_u∈V(G)f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G. Cockayne et al. [E. J. Cockayne et al. Roman domination in graphs, Discrete Mathematics 278 (2004) 11-22] showed that γ(G)≤γ_R(G)≤2γ(G) and defined a graph G to be Roman if γ_R(G)=2γ(G). In this article, the authors gave several classes of Roman graphs: P_3k,P_3k+2,C_3k,C_3k+2 for k≥1, K_m,n for min{m,n}≠2, and any graph G with γ(G)=1; In this paper, we research on regular Roman graphs and prove that: (1) the circulant graphs and , n⁄≡1 (mod (2k+1)), (n≠2k) are Roman graphs, (2) the generalized Petersen graphs P(n,2k+1)( (mod 4) and ), P(n,1) (n⁄≡2 (mod 4)), P(n,3) ( (mod 4)) and P(11,3) are Roman graphs, and (3) the Cartesian product graphs are Roman graphs.     

On subgroups of orthogonal groups of isotropic quadratic forms

Let a field K be an algebraic extension of a subfield k of characteristic not 2, n an integer, a non-degenerate isotropic form in n variables over K with coefficients in k. We study subgroups of the orthogonal group O_n(K,Q) that contain the derived subgroup Ω_n(k,Q) of the group O_n(k,Q).     

The Ramsey numbers for disjoint unions of trees

For given graphs G and H, the Ramsey numberR(G,H) is the smallest natural number n such that for every graph F of order n: either F contains G or the complement of F contains H. In this paper, we investigate the Ramsey number R(∪G,H), where G is a tree and H is a wheel W_m or a complete graph K_m. We show that if n?3, then R(kS_n,W₄)=(k+1)n for k?2, even n and R(kS_n,W₄)=(k+1)n-1 for k?1 and odd n. We also show that .     

The Ramsey numbers for disjoint unions of graphs

For given graphs G and H, the Ramsey number R(G,H) is the smallest natural number n such that for every graph F of order n: either F contains G or the complement of F contains H. In this paper we investigate the Ramsey number of a disjoint union of graphs . For any natural integer k, we contain a general upper bound, R(kG,H)?R(G,H)+(k-1)|V(G)|. We also show that if m=2n-4, 2n-8 or 2n-6, then R(kS_n,W_m)=R(S_n,W_m)+(k-1)n. Furthermore, if |G_i|>(|G_i|-|G_i+1|)(χ(H)-1) and R(G_i,H)=(χ(H)-1)(|G_i|-1)+1, for each i, then .     

On some three color Ramsey numbers for paths and cycles

For given graphs G₁,G₂,…,G_k, k≥2, the multicolor Ramsey number, denoted by R(G₁,G₂,…,G_k), is the smallest integer n such that if we arbitrarily color the edges of a complete graph on n vertices with k colors, there is always a monochromatic copy of G_i colored with i, for some 1≤i≤k. Let P_k (resp. C_k) be the path (resp. cycle) on k vertices. In the paper we consider the value for numbers of type R(P_i,P_k,C_m) for odd m, k≥m≥3 and when i is odd, and when i is even. In addition, we provide the exact values for Ramsey numbers R(P₃,P_k,C₄) for all integers k≥3.     

A new class of transitive graphs

Let n and k be integers with n≥k≥0. This paper presents a new class of graphs H(n,k), which contains hypercubes and some well-known graphs, such as Johnson graphs, Kneser graphs and Petersen graph, as its subgraphs. The authors present some results of algebraic and topological properties of H(n,k). For example, H(n,k) is a Cayley graph, the automorphism group of H(n,k) contains a subgroup of order 2ⁿn! and H(n,k) has a maximal connectivity and is hamiltonian if k is odd; it consists of two isomorphic connected components if k is even. Moreover, the diameter of H(n,k) is determined if k is odd.     

Beta-expansion and continued fraction expansion

For any real number β>1, let ε(1,β)=(ε₁(1),ε₂(1),…,εn(1),…) be the infinite β-expansion of 1. Define . Let x∈[0,1) be an irrational number. We denote by kn(x) the exact number of partial quotients in the continued fraction expansion of x given by the first n digits in the β-expansion of x. If is bounded, we obtain that for all x∈[0,1)?Q,

     

Clique partitions of complements of forests and bounded degree graphs

In this paper, we prove that for any forest F⊂K_n, the edges of E(K_n)?E(F) can be partitioned into O(nlogn) cliques. This extends earlier results on clique partitions of the complement of a perfect matching and of a hamiltonian path in K_n.In the second part of the paper, we show that for n sufficiently large and any ε∈(0,1], if a graph G has maximum degree O(n^1-ε), then the edges of E(K_n)?E(G) can be partitioned into cliques provided there exist certain Steiner systems. Furthermore, we show that there are such graphs G for which Ω(ε²n^2-2ε) cliques are required in every clique partition of E(K_n)?E(G).     

Complete solution for the rainbow numbers of matchings

For a given graph H and a positive n, the rainbow number ofH, denoted by rb(n,H), is the minimum integer k so that in any edge-coloring of K_n with k colors there is a copy of H whose edges have distinct colors. In 2004, Schiermeyer determined rb(n,kK₂) for all n≥3k+3. The case for smaller values of n (namely, ) remained generally open. In this paper we extend Schiermeyer’s result to all plausible n and hence determine the rainbow number of matchings.     

The tail is cut for Ramsey numbers of cubes

The Ramsey number R(G) of a graph G is the least integer p such that for all bicolorings of the edges of the complete graph K_p, one of the monochromatic subgraphs contains a copy of G. We show that for any positive constant c and bipartite graph G=(U,V;E) of order n where the maximum degree of vertices in U is at most , . Moreover, we show that the Ramsey number of the cube Q_n of dimension n satisfies . In both cases, the small terms are removed from the powers in the upper bounds of a earlier result of the author.     

Non-uniform Turán-type problems

Given positive integers n,k,t, with 2?k?n, and t<2^k, let m(n,k,t) be the minimum size of a family F of (nonempty distinct) subsets of [n] such that every k-subset of [n] contains at least t members of F, and every (k-1)-subset of [n] contains at most t-1 members of F. For fixed k and t, we determine the order of magnitude of m(n,k,t). We also consider related Turán numbers T_?r(n,k,t) and T_r(n,k,t), where T_?r(n,k,t) (T_r(n,k,t)) denotes the minimum size of a family such that every k-subset of [n] contains at least t members of F. We prove that T_?r(n,k,t)=(1+o(1))T_r(n,k,t) for fixed r,k,t with and n→∞.     

Complexity results in graph reconstruction

We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts c?1 of deletion:

(1)

, , , and .

(2)

For all k?2, and .

(3)

For all k?2, .

(4)

.

(5)

For all k?2, .

For many of these results, even the c=1 case was not previously known.Similar to the definition of reconstruction numbers vrn_∃(G) [F. Harary, M. Plantholt, The graph reconstruction number, J. Graph Theory 9 (1985) 451-454] and ern_∃(G) (see [J. Lauri, R. Scapellato Topics in Graph Automorphism and Reconstruction, London Mathematical Society, Cambridge University Press, Cambridge, 2003, p. 120]), we introduce two new graph parameters, vrn_∀(G) and ern_∀(G), and give an example of a family {G_n}_n?4 of graphs on n vertices for which vrn_∃(G_n)<vrn_∀(G_n). For every k?2 and n?1, we show that there exists a collection of k graphs on (2^k-1+1)n+k vertices with 2ⁿ 1-vertex-preimages, i.e., one has families of graph collections whose number of 1-vertex-preimages is huge relative to the size of the graphs involved.     

Large induced subgraphs with equated maximum degree

For a graph G, denote by f_k(G) the smallest number of vertices that must be deleted from G so that the remaining induced subgraph has its maximum degree shared by at least k vertices. It is not difficult to prove that there are graphs for which already , where n is the number of vertices of G. It is conjectured that for every fixed k. We prove this for k=2,3. While the proof for the case k=2 is easy, already the proof for the case k=3 is considerably more difficult. The case k=4 remains open.A related parameter, s_k(G), denotes the maximum integer m so that there are k vertex-disjoint subgraphs of G, each with m vertices, and with the same maximum degree. We prove that for every fixed k, s_k(G)≥n/k−o(n). The proof relies on probabilistic arguments.     

Dense edge-magic graphs and thin additive bases

A graph G of order n and size m is edge-magic if there is a bijection l:V(G)∪E(G)→[n+m] such that all sums l(a)+l(b)+l(ab), ab∈E(G), are the same. We present new lower and upper bounds on M(n), the maximum size of an edge-magic graph of order n, being the first to show an upper bound of the form . Concrete estimates for ε can be obtained by knowing s(k,n), the maximum number of distinct pairwise sums that a k-subset of [n] can have.So, we also study s(k,n), motivated by the above connections to edge-magic graphs and by the fact that a few known functions from additive number theory can be expressed via s(k,n). For example, our estimate

     

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.     

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).