On the Laplacian spectral radii of trees

Let Δ(T) and μ(T) denote the maximum degree and the Laplacian spectral radius of a tree T, respectively. Let T_n be the set of trees on n vertices, and . In this paper, we determine the two trees which take the first two largest values of μ(T) of the trees T in when . And among the trees in , the tree which alone minimizes the Laplacian spectral radius is characterized. We also prove that for two trees T₁ and T₂ in , if Δ(T₁)>Δ(T₂) and , then μ(T₁)>μ(T₂). As an application of these results, we give a general approach about extending the known ordering of trees in T_n by their Laplacian spectral radii.     

How to play the Majority game with a liar

The Majority game is played by a questioner () and an answerer (). holds n elements, each of which can be labeled as 0 or 1. is trying to identify some element holds as having the Majority label or, in the case of a tie, claim there is none. To do this asks questions comparing whether two elements have the same or different label. ’s goal is to ask as few questions as possible while ’s goal is to delay as much as possible. Let q^∗ denote the minimal number of questions needed for to identify a Majority element regardless of ’s answers.In this paper we investigate upper and lower bounds for q^∗ in a variation of the Majority game, where is allowed to lie up to t times. We consider two versions of the game, the adaptive (where questions are asked sequentially) and the oblivious (where questions are asked in one batch).     

Game colouring of the square of graphs

This paper studies the game chromatic number and game colouring number of the square of graphs. In particular, we prove that if G is a forest of maximum degree Δ≥9, then , and there are forests G with . It is also proved that for an outerplanar graph G of maximum degree Δ, , and for a planar graph G of maximum degree Δ, .     

On the number of graphs with a given endomorphism monoid

For a given finite monoid , let be the number of graphs on n vertices with endomorphism monoid isomorphic to . For any nontrivial monoid we prove that where and are constants depending only on with .For every k there exists a monoid of size k with , on the other hand if a group of unity of has a size k>2 then .     

Constructions of optimal quaternary constant weight codes via group divisible designs

Generalized Steiner systems were first introduced by Etzion and used to construct optimal constant weight codes over an alphabet of size g+1 with minimum Hamming distance 2k−3, in which each codeword has length v and weight k. As to the existence of a , a lot of work has been done for k=3, while not so much is known for k=4. The notion k-^∗GDD was first introduced by Chen et al. and used to construct . The necessary condition for the existence of a is v≥14. In this paper, it is proved that there exists a for any prime power and v≥19. By using this result, the known results on the existence of optimal quaternary constant weight codes are then extended.     

Directed 3-cycle decompositions of complete directed graphs with quadratic leaves

Let G be a vertex-disjoint union of directed cycles in the complete directed graph D_t, let |E(G)| be the number of directed edges of G and suppose or if t=5, and if t=6. It is proved in this paper that for each positive integer t, there exist -decompositions for D_t−G if and only if .     

Total colorings and list total colorings of planar graphs without intersecting 4-cycles

Suppose that G is a planar graph with maximum degree Δ and without intersecting 4-cycles, that is, no two cycles of length 4 have a common vertex. Let χ^″(G), and denote the total chromatic number, list edge chromatic number and list total chromatic number of G, respectively. In this paper, it is proved that χ^″(G)=Δ+1 if Δ≥7, and and if Δ(G)≥8. Furthermore, if G is a graph embedded in a surface of nonnegative characteristic, then our results also hold.     

A note on an embedding problem in transitive tournaments

Let TT_n be a transitive tournament on n vertices. It is known Görlich, Pil?niak, Wo?niak, (2006) [3] that for any acyclic oriented graph of order n and size not greater than , two graphs isomorphic to are arc-disjoint subgraphs of TT_n. In this paper, we consider the problem of embedding of acyclic oriented graphs into their complements in transitive tournaments. We show that any acyclic oriented graph of size at most is embeddable into all its complements in TT_n. Moreover, this bound is generally the best possible.     

On signed cycle domination in graphs

Let G=(V,E) be a graph, a function f:E→{−1,1} is said to be an signed cycle dominating function (SCDF) of G if ∑_e∈E(C)f(e)≥1 holds for any induced cycle C of G. The signed cycle domination number of G is defined as is an SCDF of G}. In this paper, we obtain bounds on , characterize all connected graphs G with , and determine the exact value of for some special classes of graphs G. In addition, we pose some open problems and conjectures.     

Another step towards proving a conjecture by Plummer and Toft

A cyclic colouring of a graph G embedded in a surface is a vertex colouring of G in which any two distinct vertices sharing a face receive distinct colours. The cyclic chromatic number of G is the smallest number of colours in a cyclic colouring of G. Plummer and Toft in 1987 [M.D. Plummer, B. Toft, Cyclic coloration of 3-polytopes, J. Graph Theory 11 (1987) 507-515] conjectured that for any 3-connected plane graph G with maximum face degree Δ^∗. It is known that the conjecture holds true for Δ^∗≤4 and Δ^∗≥24. The validity of the conjecture is proved in the paper for Δ^∗≥18.     

On wreathed lexicographic products of graphs

This paper proves a necessary and sufficient condition for the endomorphism monoid of a lexicographic product G[H] of graphs G,H to be the wreath product of the monoids and . The paper also gives respective necessary and sufficient conditions for specialized cases such as for unretractive or triangle-free graphs G.     

Perfectness and imperfectness of unit disk graphs on triangular lattice points

Given a finite set of 2-dimensional points P⊆R² and a positive real d, a unit disk graph, denoted by (P,d), is an undirected graph with vertex set P such that two vertices are adjacent if and only if the Euclidean distance between the pair is less than or equal to d. Given a pair of non-negative integers m and n, P(m,n) denotes a subset of 2-dimensional triangular lattice points defined by where . Let T_m,n(d) be a unit disk graph defined on a vertex set P(m,n) and a positive real d. Let be the kth power of T_m,n(1).In this paper, we show necessary and sufficient conditions that [ is perfect] and/or [ is perfect], respectively. These conditions imply polynomial time approximation algorithms for multicoloring (T_m,n(d),w) and .     

Combinatorially fruitful properties of 3⋅2 and 3⋅2 modulo p

Write a≡3⋅2⁻¹ and where p is an odd prime. Let c be a value that is congruent (modp) to either a or b. For any x from Z_p?{0}, evaluate each of x and within the interval (0,p). Then consider the quantity where the differences are evaluated in the interval (0,p−1), and the quantity where the differences are evaluated (modp+1) in the interval (0,p+1). As x varies over Z_p?{0}, the values of each of and give exactly two occurrences of nearly every member of 1,2,…,(p−1)/2. This fact enables a and b to be used in constructing some terraces for Z_p−1 and Z_p+1 from segments of elements that are themselves initially evaluated in Z_p.     

A tripling construction for overlarge sets of KTS

An overlarge set of , denoted by , is a collection {(X?{x},B_x):x∈X}, where X is a (v+1)-set, each (X?{x},B_x) is a and {B_x:x∈X} forms a partition of all triples on X. In this paper, we give a tripling construction for overlarge sets of KTS. Our main result is that: If there exists an with a special property, then there exists an . It is obtained that there exists an for u=2²ⁿ⁻¹−1 or u=qⁿ, where prime power q≡7 (mod 12) and m≥0,n≥1.     

Extension of Fourier algebra homomorphisms to duals of algebras of uniformly continuous functionals

For a locally compact group G, let XG be one of the following introverted subspaces of VN(G): , the C^∗-algebra of uniformly continuous functionals on A(G); , the space of weakly almost periodic functionals on A(G); or , the C^∗-algebra generated by the left regular representation on the measure algebra of G. We discuss the extension of homomorphisms of (reduced) Fourier-Stieltjes algebras on G and H to cb-norm preserving, weak^∗-weak^∗-continuous homomorphisms of into , where (XG,XH) is one of the pairs , , or . When G is amenable, these extensions are characterized in terms of piecewise affine maps.     

On the signed edge domination number of graphs

Let be the signed edge domination number of G. In 2006, Xu conjectured that: for any 2-connected graph G of order n(n≥2), . In this article we show that this conjecture is not true. More precisely, we show that for any positive integer m, there exists an m-connected graph G such that . Also for every two natural numbers m and n, we determine , where K_m,n is the complete bipartite graph with part sizes m and n.     

A generalization of a conjecture due to Erd?s, Jacobson and Lehel

An r-graph is a loopless undirected graph in which no two vertices are joined by more than r edges. An r-complete graph on m+1 vertices, denoted by , is an r-graph on m+1 vertices in which each pair of vertices is joined by exactly r edges. A non-increasing sequence π=(d₁,d₂,…,d_n) of nonnegative integers is r-graphic if it is realizable by an r-graph on n vertices. Let be the smallest even integer such that each n-term r-graphic sequence with term sum of at least is realizable by an r-graph containing as a subgraph. In this paper, we determine the value of for sufficiently large n, which generalizes a conjecture due to Erd?s, Jacobson and Lehel.     

On (d,1)-total numbers of graphs

A (d,1)-total labelling of a graph G assigns integers to the vertices and edges of G such that adjacent vertices receive distinct labels, adjacent edges receive distinct labels, and a vertex and its incident edges receive labels that differ in absolute value by at least d. The span of a (d,1)-total labelling is the maximum difference between two labels. The (d,1)-total number, denoted , is defined to be the least span among all (d,1)-total labellings of G. We prove new upper bounds for , compute some for complete bipartite graphs K_m,n, and completely determine all for d=1,2,3. We also propose a conjecture on an upper bound for in terms of the chromatic number and the chromatic index of G.     

Ore-type conditions implying 2-factors consisting of short cycles

For every graph G, let . The main result of the paper says that every n-vertex graph G with contains each spanning subgraph H all whose components are isomorphic to graphs in . This generalizes the earlier results of Justesen, Enomoto, and Wang, and is a step towards an Ore-type analogue of the Bollobás-Eldridge-Catlin Conjecture.     

The orientable genus of some joins of complete graphs with large edgeless graphs

In an earlier paper the authors showed that with one exception the nonorientable genus of the graph with m≥n−1, the join of a complete graph with a large edgeless graph, is the same as the nonorientable genus of the spanning subgraph . The orientable genus problem for with m≥n−1 seems to be more difficult, but in this paper we find the orientable genus of some of these graphs. In particular, we determine the genus of when n is even and m≥n, the genus of when n=2^p+2 for p≥3 and m≥n−1, and the genus of when n=2^p+1 for p≥3 and m≥n+1. In all of these cases the genus is the same as the genus of K_m,n, namely ⌈(m−2)(n−2)/4⌉.