Set systems without a 3-simplex

A 3-simplex is a collection of four sets A₁,…,A₄ with empty intersection such that any three of them have nonempty intersection. We show that the maximum size of a set system on n elements without a 3-simplex is for all n≥1, with equality only achieved by the family of sets containing a given element or of size at most 2. This extends a result of Keevash and Mubayi, who showed the conclusion for n sufficiently large.     

The order of hypotraceable oriented graphs

A digraph of order n is hypotraceable if it is nontraceable but all its induced subdigraphs of order n−1 are traceable. Grötschel et al. (1980) [M. Grötschel, C. Thomassen, Y. Wakabayashi, Hypotraceable digraphs, J. Graph Theory 4 (1980) 377–381] constructed an infinite family of hypotraceable oriented graphs, the smallest of which has order 13. We show that there exist hypotraceable oriented graphs of order n for every n≥8 except possibly for n=9,11 and that is the only one of order less than 8.Furthermore, we determine all the hypotraceable oriented graphs of order 8 and explain the relevance of these results to the problem of determining, for given k≥2, the maximum order of nontraceable oriented digraphs each of whose induced subdigraphs of order k is traceable.     

Graphic sequences with a realization containing a complete multipartite subgraph

A nonincreasing sequence of nonnegative integers π=(d₁,d₂,…,d_n) is graphic if there is a (simple) graph G of order n having degree sequence π. In this case, G is said to realizeπ. For a given graph H, a graphic sequence π is potentiallyH-graphic if there is some realization of π containing H as a (weak) subgraph. Let σ(π) denote the sum of the terms of π. For a graph H and n∈Z⁺, σ(H,n) is defined as the smallest even integer m so that every n-term graphic sequence π with σ(π)≥m is potentially H-graphic. Let denote the complete t partite graph such that each partite set has exactly s vertices. We show that and obtain the exact value of σ(K_j+K_s,s,n) for n sufficiently large. Consequently, we obtain the exact value of for n sufficiently large.     

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.     

A construction of imprimitive symmetric graphs which are not multicovers of their quotients

Let Σ be a finite X-symmetric graph of valency , and s≥1 an integer. In this article we give a sufficient and necessary condition for the existence of a class of finite imprimitive (X,s)-arc-transitive graphs which have a quotient isomorphic to Σ and are not multicovers of that quotient, together with a combinatorial method, called the double-star graph construction, for constructing such graphs. Moreover, for any X-symmetric graph Γ admitting a nontrivial X-invariant partition B such that Γ is not a multicover of Γ_B, we show that there exists a sequence of -invariant partitions B=B₀,B₁,…,B_m of V(Γ), where m≥1 is an integer, such that B_i is a proper refinement of B_i−1, Γ_Bi is not a multicover of Γ_Bi−1 and Γ_Bi can be reconstructed from Γ_Bi−1 by the double-star graph construction, for i=1,2,…,m, and that either Γ≅Γ_Bm or Γ is a multicover of Γ_Bm.     

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.     

Vertex-transitive self-complementary uniform hypergraphs of prime order

For an integer n and a prime p, let . In this paper, we present a construction for vertex-transitive self-complementary k-uniform hypergraphs of order n for each integer n such that for every prime p, where ?=max{k₍₂₎,(k−1)₍₂₎}, and consequently we prove that the necessary conditions on the order of vertex-transitive self-complementary uniform hypergraphs of rank k=2^? or k=2^?+1 due to Potoňick and Šajna are sufficient. In addition, we use Burnside’s characterization of transitive groups of prime degree to characterize the structure of vertex-transitive self-complementary k-hypergraphs which have prime order p in the case where k=2^? or k=2^?+1 and , and we present an algorithm to generate all of these structures. We obtain a bound on the number of distinct vertex-transitive self-complementary graphs of prime order , up to isomorphism.     

Graph designs for the eight-edge five-vertex graphs

The existence of graph designs for the two nonisomorphic graphs on five vertices and eight edges is determined in the case of index one, with three possible exceptions in total. It is established that for the unique graph with vertex sequence (3, 3, 3, 3, 4), a graph design of order n exists exactly when and n≠16, with the possible exception of n=48. For the unique graph with vertex sequence (2,3,3,4,4), a graph design of order n exists exactly when , with the possible exceptions of n∈{32,48}.     

Generalized homothetic biorders

In this paper, we study the binary relations R on a nonempty N^∗-set A which are h-independent and h-positive (cf. the introduction below). They are called homothetic positive orders. Denote by B the set of intervals of R having the form [r,+∞[ with 0<r≤+∞ or ]q,∞[ with q∈Q_≥0. It is a Q_>0-set endowed with a binary relation > extending the usual one on R_>0 (identified with a subset of B via the map r?[r,+∞[). We first prove that there exists a unique map Φ_R:A×A→B such that (for all and all ) we have Φ(mx,ny)=mn⁻¹⋅Φ(x,y) and . Then we give a characterization of the homothetic positive orders R on A such that there exist two morphisms of N^∗-sets satisfying . They are called generalized homothetic biorders. Moreover, if we impose some natural conditions on the sets u₁(A) and u₂(A), the representation (u₁,u₂) is “uniquely” determined by R. For a generalized homothetic biorder R on A, the binary relation R₁ on A defined by is a generalized homothetic weak order; i.e. there exists a morphism of N^∗-sets u:A→B such that (for all ) we have . As we did in [B. Lemaire, M. Le Menestrel, Homothetic interval orders, Discrete Math. 306 (2006) 1669-1683] for homothetic interval orders, we also write “the” representation (u₁,u₂) of R in terms of u and a twisting factor.     

A sufficient condition for pancyclability of graphs

Let G be a graph of order n and S be a vertex set of q vertices. We call G,S-pancyclable, if for every integer i with 3≤i≤q there exists a cycle C in G such that |V(C)∩S|=i. For any two nonadjacent vertices u,v of S, we say that u,v are of distance two in S, denoted by d_S(u,v)=2, if there is a path P in G connecting u and v such that |V(P)∩S|≤3. In this paper, we will prove that if G is 2-connected and for all pairs of vertices u,v of S with d_S(u,v)=2, , then there is a cycle in G containing all the vertices of S. Furthermore, if for all pairs of vertices u,v of S with d_S(u,v)=2, , then G is S-pancyclable unless the subgraph induced by S is in a class of special graphs. This generalizes a result of Fan [G. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory B 37 (1984) 221-227] for the case when S=V(G).     

Bounds on isoperimetric values of trees

Let G=(V,E) be a finite, simple and undirected graph. For S⊆V, let δ(S,G)={(u,v)∈E:u∈S and v∈V−S} be the edge boundary of S. Given an integer i, 1≤i≤|V|, let the edge isoperimetric value of G at i be defined as b_e(i,G)=min_S⊆V;|S|=i|δ(S,G)|. The edge isoperimetric peak of G is defined as b_e(G)=max_1≤j≤|V|b_e(j,G). Let b_v(G) denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete t-ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete k-ary trees, Discrete Mathematics, in press (doi:10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) trees.The depth d of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth d (denoted as ), and where c₁, c₂ are constants. For a complete t-ary tree of depth d (denoted as ) and d≥clogt where c is a constant, we show that and where c₁, c₂ are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete t-ary tree. Let T=(V,E,r) be a finite, connected and rooted tree — the root being the vertex r. Define a weight function w:V→N where the weight w(u) of a vertex u is the number of its successors (including itself) and let the weight index η(T) be defined as the number of distinct weights in the tree, i.e η(T)=|{w(u):u∈V}|. For a positive integer k, let ?(k)=|{i∈N:1≤i≤|V|,b_e(i,G)≤k}|. We show that .     

A multiply intersecting Erd?s-Ko-Rado theorem — The principal case

Let m(n,k,r,t) be the maximum size of satisfying |F₁∩?∩F_r|≥t for all F₁,…,F_r∈F. We prove that for every p∈(0,1) there is some r₀ such that, for all r>r₀ and all t with 1≤t≤⌊(p^1−r−p)/(1−p)⌋−r, there exists n₀ so that if n>n₀ and p=k/n, then . The upper bound for t is tight for fixed p and r.     

Colouring games on outerplanar graphs and trees

Let f be a graph function which assigns to each graph H a non-negative integer f(H)≤|V(H)|. The f-game chromatic number of a graph G is defined through a two-person game. Let X be a set of colours. Two players, Alice and Bob, take turns colouring the vertices of G with colours from X. A partial colouring c of G is legal (with respect to graph function f) if for any subgraph H of G, the sum of the number of colours used in H and the number of uncoloured vertices of H is at least f(H). Both Alice and Bob must colour legally (i.e., the partial colouring produced needs to be legal). The game ends if either all the vertices are coloured or there are uncoloured vertices with no legal colour. In the former case, Alice wins the game. In the latter case, Bob wins the game. The f-game chromatic number of G, χ_g(f,G), is the least number of colours that the colour set X needs to contain so that Alice has a winning strategy. Let be the graph function defined as , for any n≥3 and otherwise. Then is called the acyclic game chromatic number of G. In this paper, we prove that any outerplanar graph G has acyclic game chromatic number at most 7. For any integer k, let ?_k be the graph function defined as ?_k(K₂)=2 and ?_k(P_k)=3 (P_k is the path on k vertices) and ?_k(H)=0 otherwise. This paper proves that if k≥8 then for any tree T, χ_g(?_k,T)≤9. On the other hand, if k≤6, then for any integer n, there is a tree T such that χ_g(?_k,T)≥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.     

Variations of Y-dominating functions on graphs

Let Y be a subset of real numbers. A Y-dominating function of a graph G=(V,E) is a function f:V→Y such that for all vertices v∈V, where N_G[v]={v}∪{u|(u,v)∈E}. Let for any subset S of V and let f(V) be the weight of f. The Y-domination problem is to find a Y-dominating function of minimum weight for a graph G=(V,E). In this paper, we study the variations of Y-domination such as {k}-domination, k-tuple domination, signed domination, and minus domination for some classes of graphs. We give formulas to compute the {k}-domination, k-tuple domination, signed domination, and minus domination numbers of paths, cycles, n-fans, n-wheels, n-pans, and n-suns. Besides, we present a unified approach to these four problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. This paper also gives complexity results for the problems on doubly chordal graphs, dually chordal graphs, bipartite planar graphs, chordal bipartite graphs, and planar graphs.     

Turán’s theorem inverted

In this note we complete an investigation started by Erd?s in 1963 that aims to find the strongest possible conclusion from the hypothesis of Turán’s theorem in extremal graph theory.Let be the complete r-partite graph with parts of sizes s₁≥2,s₂,…,s_r with an edge added to the first part. Letting t_r(n) be the number of edges of the r-partite Turán graph of order n, we prove that:For all r≥2 and all sufficiently small c>0, every graph of sufficiently large order n with t_r(n)+1 edges contains a .We also give a corresponding stability theorem and two supporting results of wider scope.     

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 Δ, .     

Linkability in iterated line graphs

We prove that for every graph H with the minimum degree δ?5, the third iterated line graph L³(H) of H contains as a minor. Using this fact we prove that if G is a connected graph distinct from a path, then there is a number k_G such that for every i?k_G the i-iterated line graph of G is -linked. Since the degree of Lⁱ(G) is even, the result is best possible.     

On symmetric graphs of valency five

A graph X, with a subgroup G of the automorphism group of X, is said to be (G,s)-transitive, for some s≥1, if G is transitive on s-arcs but not on (s+1)-arcs, and s-transitive if it is -transitive. Let X be a connected (G,s)-transitive graph, and G_v the stabilizer of a vertex v∈V(X) in G. If X has valency 5 and G_v is solvable, Weiss [R.M. Weiss, An application of p-factorization methods to symmetric graphs, Math. Proc. Camb. Phil. Soc. 85 (1979) 43-48] proved that s≤3, and in this paper we prove that G_v is isomorphic to the cyclic group Z₅, the dihedral group D₁₀ or the dihedral group D₂₀ for s=1, the Frobenius group F₂₀ or F₂₀×Z₂ for s=2, or F₂₀×Z₄ for s=3. Furthermore, it is shown that for a connected 1-transitive Cayley graph of valency 5 on a non-abelian simple group G, the automorphism group of is the semidirect product , where R(G) is the right regular representation of G and .     

On the minimum real roots of the adjoint polynomial of a graph

For a graph G, we denote by h(G,x) the adjoint polynomial of G. Let β(G) denote the minimum real root of h(G,x). In this paper, we characterize all the connected graphs G with .