Minimally k-connected graphs of low order and maximal size

Let G be a minimally k-connected graph of order n and size e(G).Mader [4] proved that (i) $\text{e(G)?kn?(}\text{k+1}\text{2}\text{)}$; (ii) e(G)?k(n?k) if n?3k?2, and the complete bipartite graph K_k,n?k is the only minimally k-connected graph of order; n and size k(n?k) when k?2 and n?3k?1.The purpose of the present paper is to determine all minimally k-connected graphs of low order and maximal size. For each n such that k+1?n?3k?2 we prove $\text{e(G)??}\text{(n+k)}{}^2\text{8}\text{?}$ and characterize all minimally k-connected graphs of order n and size $\text{?(}\text{(n+k)}{}^2\text{8}\text{?}$.     

On subgraph number independence in trees

For finite graphs F and G, let N_F(G) denote the number of occurrences of F in G, i.e., the number of subgraphs of G which are isomorphic to F. If $\text{F}$ and $\text{G}$ are families of graphs, it is natural to ask then whether or not the quantities N_F(G), F∈$\text{F}$, are linearly independent when G is restricted to $\text{G}$. For example, if $\text{F}$ = {K₁, K₂} (where K_n denotes the complete graph on n vertices) and $\text{F}$ is the family of all (finite) trees, then of course N_K1(T) ? N_K2(T) = 1 for all T∈$\text{F}$. Slightly less trivially, if $\text{F}$ = {S_n: n = 1, 2, 3,…} (where S_n denotes the star on n edges) and $\text{G}$ again is the family of all trees, then Σ_n=1^∞(?1)ⁿ⁺¹N_Sn(T)=1 for all T∈$\text{G}$. It is proved that such a linear dependence can never occur if $\text{F}$ is finite, no F∈$\text{F}$ has an isolated point, and $\text{G}$ contains all trees. This result has important applications in recent work of L. Lovász and one of the authors (Graham and Lovász, to appear).     

On n-hamiltonian graphs

A graph G of order p ? 3 is called n-hamiltonian, 0 ? n ? p ? 3, if the removal of any m vertices, 0 ? m ? n, results in a hamiltonian graph. A graph G of order p ? 3 is defined to be n-hamiltonian, ?p ? n ? 1, if there exists ?n or fewer pairwise disjoint paths in G which collectively span G. Various conditions in terms of n and the degrees of the vertices of a graph are shown to be sufficient for the graph to be n-hamiltonian for all possible values of n. It is also shown that if G is a graph of order p ? 3 and $\text{K}\text{(G) ? β(G) + n (?p ? n ? p ? 3)}$, then G is n-hamiltonian.     

On k-sequential and other numbered graphs

The concept of a k-sequential graph is presented as follows. A graph G with ∣V(G)∪ E(G)∣=t is called k-sequential if there is a bijection$\text{?: V(G)∪E(G) → {k,k+1,…,t+k?1}}$ such that for each edge$\text{e}\text{?}\text{=xy}$in E(G) one has$\text{?(}\text{e}\text{?}\text{) = ∣?(x)??(y)∣}$. A graph that is 1-sequential is called simply sequential, and, in particular the author has conjectured that all trees are simply sequential. In this paper an introductory study of k-sequential graphs is made. Further, several variations on the problems of gracefully or sequentially numbering the elements of a graph are discussed.     

Construction of matroidal families by partly closed sets

A matroidal family of graphs is a set $\text{M}$≠Ø of connected finite graphs such that for every finite graph G the edge sets of those subgraphs of G which are isomorphic to some element of $\text{M}$ are the circuits of a matroid on the edge set of G. In [9], Schmidt shows that, for n?0, ?2n<r?1, n, $\text{r∈}\text{Z}$, the set $\text{M}\text{(n, r)={G∣G}$ is a graph with β(G)=nα(G)+r and α(G )>, and is minimal with this property (with respect to the relation ?))} is a matroidal family of graphs. He also describes a method to construct new matroidal families of graphs by means of so-called partly closed sets. In this paper, an extension of this construction is given. By means of s-partly closed subsets of $\text{M}\text{(n, r)}$, s?r, we are able to give sufficient and necessary conditions for a subset $\text{P}\text{(n, r)}$ of $\text{M}\text{(n, r)}$ to yield a matroidal family of graphs when joined with the set $\text{I}\text{(n, s)}$ of all graphs $\text{G∈}\text{M}\text{(n, s)}$ which satisfy: If $\text{H∈}\text{P}\text{(n, r)}$, then H?G. In particular, it is shown that $\text{M}\text{(n, r)}$ is not a matroidal family of graphs for r?2. Furthermore, for n?0, 1?2n<r, n, $\text{r∈}\text{Z}$, the set of bipartite elements of $\text{M}\text{(n, r)}$ can be used to construct new matroidal families of graphs if and only if s?min(n+r, 1).     

Connected graphs with maximal Q-index: The one-dominating-vertex case

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then H_n,k, the graph obtained from the star K_1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.     

Some Ramsey numbers for directed graphs

Given k directed graphs G₁,…,G_k the Ramsey number R(G₁,…, G_k) is the smallest integer n such that for any partition (U₁,…,U_k) of the arcs of the complete symmetric directed graph K_n, there exists an integer i such that the partial graph generated by U₁ contains G₁ as a subgraph. In the article we give a necessary and sufficient condition for the existence of Ramsey numbers, and, when they exist an upper bound function. We also give exact values for some classes of graphs. Our main result is: $\text{R(}\text{P}{}_{\mathrm{n}}\text{,….}\text{P}{}_{\mathrm{nk-1}}\text{, G) = n}{}_1\text{…n}{}_{\mathrm{k-1}}\text{(p-1) + 1}$, where G is a hamltonian directed graph with p vertices and $\text{P}{}_{\mathrm{n}}{}_{\mathrm{i}}$ denotes the directed path of length n_t     

On the minimum order of graphs with given semigroup

Denote by M(n) the smallest positive integer such that for every n-element monoid M there is a graph G with at most M(n) vertices such that End(G) is isomorphic to M. It is proved that $\text{2}\text{(1 + o(1))n}\text{log}{}_2\text{n}\text{≤M(n)≤n ·}\text{2n}\text{+ O(n)}$. Moreover, for almost all n-element monoids M there is a graph G with at most 12 · n · log₂n + n vertices such that End(G) is isomorphic to M.     

Properties of connected graphs having minimum degree distance

The degree distance of a connected graph, introduced by Dobrynin, Kochetova and Gutman, has been studied in mathematical chemistry. In this paper some properties of graphs having minimum degree distance in the class of connected graphs of order n and size m≥n−1 are deduced. It is shown that any such graph G has no induced subgraph isomorphic to P₄, contains a vertex z of degree n−1 such that G−z has at most one connected component C such that |C|≥2 and C has properties similar to those of G.For any fixed k such that k=0,1 or k≥3, if m=n+k and n≥k+3 then the extremal graph is unique and it is isomorphic to K₁+(K_1,k+1∪(n−k−3)K₁).     

On pancyclic digraphs

We show that a strongly connected digraph with n vertices and minimum degree ? n is pancyclic unless it is one of the graphs K_p,p. This generalizes a result of A. Ghouila-Houri. We disprove a conjecture of J. A. Bondy by showing that there exist hamiltonian digraphs with n vertices and $\text{1}\text{2}\text{n(n + 1) – 3}$ edges which are not pancyclic. We show that any hamiltonian digraph with n vertices and at least $\text{1}\text{2}\text{n(n + 1) – 1}$ edges is pancyclic and we give some generalizations of this result. As applications of these results we determine the minimal number of edges required in a digraph to guarantee the existence of a cycle of length k, k ? 2, and we consider the corresponding problem where the digraphs under consideration are assumed to be strongly connected.     

Connected matroids with the smallest whitney numbers

In “The Slimmest Geometric Lattices” (Trans. Amer. Math. Soc.). Dowling and Wilson showed that if G is a combinatorial geometry of rank r(G) = n, and if _X(G) = Σμ(0, x)λ^{r ? r(x)} = Σ (?1)^{r ? k}W_kλ^k is the characteristic polynomial of G, then

$\text{w}{}_{\mathrm{k}}\text{?}\text{r}\text{k}\text{+n}\text{r?1}\text{k}$

Thus γ(G) ? 2^{r ? 1} (n+2), where γ(G) = Σw_k. In this paper we sharpen these lower bounds for connected geometries: If G is connected, r(G) ? 3, and n(G) ? 2 ((r, n) ≠ (4,3)), then

$\text{w}{}_{\mathrm{i}}\text{?}\text{r}\text{i}\text{+ n}\text{r}\text{i+1}\text{for i>1; w}{}_1\text{?r+n}\text{r}\text{2}\text{? 1;}$

|μ| ? (r? 1)n; and γ ? (2^{r ? 1} ? 1)(2n + 2). These bounds are all achieved for the parallel connection of an r-point circuit and an (n + 1)point line. If G is any series-parallel network, $\text{r(G) = r(}\text{G}\text{?}\text{) = 4}$, and $\text{n(G) = n(}\text{G}\text{?}\text{) = 3}$ then $\text{(w}{}_1\text{(G))}{}^4{}_{\mathrm{t-G}}\text{? (w}{}_1\text{(}\text{G}\text{?}\text{)) = (8, 20, 18, 7, 1)}$. Further, if β is the Crapo invariant,

$\text{β(G)=}\text{d}{}_{\mathrm{X}}\text{(G)}\text{dλ}\text{(1)}\text{,}$

then β(G) ? max(1, n ? r + 2). This lower bound is achieved by the parallel connection of a line and a maximal size series-parallel network.     

Linear arboricity for graphs with multiple edges

Akiyama, Exoo, and Harary conjectured that for any simple graph G with maximum degree Δ(G), the linear arboricity la(G) satisfies ?Δ(G)/2? ≦ la(G) ≦ ?(Δ(G) + 1)/2?. Here it is proved that if G is a loopless graph with maximum degree Δ(G) ≦ k and maximum edge multiplicity μ(G) ≦ k ? 2ⁿ⁺¹ + 1, where k ≧ 2^n?2, then la(G) ≦ k ? 2ⁿ. It is also conjectured that for any loopless graph G, ?Δ(G)/2? ≦ la(G) ≦ ?(Δ(G) + μ(G))/2?.     

Bounds for sorting by prefix reversal

For a permutation σ of the integers from 1 to n, let ?(σ) be the smallest number of prefix reversals that will transform σ to the identity permutation, and let ?(n) be the largest such ?(σ) for all σ in (the symmetric group) S_n. We show that $\text{?(n)?}\text{(5n+5)}\text{3}$, and that $\text{?(n)?}\text{17n}\text{16}$ for n a multiple of 16. If, furthermore, each integer is required to participate in an even number of reversed prefixes, the corresponding function g(n) is shown to obey $\text{3n}\text{2?1}\text{?g(n)?2n+3}$.     

Comparability graphs and intersection graphs

A function diagram (f-diagram) D consists of the family of curves {$\text{1}\text{?}$ñ} obtained from n continuous functions $\text{f}{}_{\mathrm{i}}\text{:[0,1]→}\text{R}\text{(1?i?n)}$. We call the intersection graph of D a function graph (f-graph). It is shown that a graph G is an f-graph if and only if its complement ? is a comparability graph. An f-diagram generalizes the notion of a permulation diagram where the f_i are linear functions. It is also shown that G is the intersection graph of the concatenation of ?k permutation diagrams if and only if the partial order dimension of $\text{G}\text{?}\text{is ?k+1}$. Computational complexity results are obtained for recognizing such graphs.     

On a valence problem in extremal graph theory

Let L ≠ Kinp be a p-chromatic graph and e be an edge of L such that L ? e is (p?1)-chromatic If Gⁿ is a graph of n vertices without containing L but containing K_p, then the minimum valence of Gⁿ is

$\text{?n}\text{1?}\text{1}\text{p?}\text{3}\text{2}\text{+}\text{O}\text{(1).}$

     

Bounds on path connectivity

The path-connectivity of a graph G is the maximal k for which between any k pairs of vertices there are k edge-disjoint paths (one between each pair). An upper bound for the path-connectivity of n^q(q<1) separable graphs [6] is shown to exist.If the edge-connectivity of a graph is K_E then between any two pairs of vertices and for every $\text{t?}\text{K}{}_{\mathrm{E}}$ there exists a t?t′?t+1 such that there are t′ paths between the first pair and $\text{K}{}_{\mathrm{E}}\text{?t′}$ between the second pair. All paths are edge-disjoint.     

On a problem of Chvátal and Erdös on hypergraphs containing no generalized simplex

Let X be an n-element set and $\text{T}$ a family of k-subsets of X. Let r be an integer, k > r ? 2. Suppose that $\text{T}$ does not contain r + 1 members having empty intersection such that any r of them intersect non-trivially. Chvátal and Erdös conjectured that for (r + 1) k ? rn we have |$\text{F}$|$\text{?}\text{n?1}\text{k?1}$. In this paper we first prove that This conjecture holds asymptotically (Theory 1). In Theorems 4 and 5 we prove it for r = 2, K ? 5, n > n_o(k); k ? 3r, n > n_o(k, r), respectively.     

The interval number of a complete multipartite graph

The interval number of a graph G, denoted i(G), is the least positive integer t for which G is the intersection graph of a family of sets each of which is the union of at most t closed intervals of the real line $\text{R}$. Trotter and Harary showed that the interval number of the complete bipartite graph K(m,n) is $\text{?}\text{(mn + 1)}\text{(m + n)}\text{?}$. Matthews showed that the interval number of the complete multipartite graph K(n₁,n₂,…,n_p) was the same as the interval number of K(n₁,n₂) when n₁ = n₂ = ? = n_p. Trotter and Hopkins showed that i(K(n₁,n₂,…,n_p)) ≤ 1 + i(K(n₁,n₂)) whenever p ≥ 2 and n₁≥n₂≥ ? ≥n_p. West showed that for each n ≥ 3, there exists a constant c_n so that if p ≥ c_n,n₁ = n²?n ?1, and n₂ = n₃ = ? n_p = n, then i(K(n₁,n₂,…,n_p) = 1 + i(K(n₁, n₂)). In view of these results, it is natural to consider the problem of determining those pairs (n₁,n₂) with n₁ ≥ n₂ so that i(K(n₂,…,n_p)) = i(K(n₁,n₂)) whenever p ≥ 2 and n₂ ≥ n₃ ≥ ? ≥ n_p. In this paper, we present constructions utilizing Eulerian circuits in directed graphs to show that the only exceptional pairs are (n² ? n ? 1, n) for n ≥ 3 and (7,5).     

The number of Hamiltonian circuits

G = 〈V(G), E(G)〉 denotes a directed graph without loops and multiple arrows. $\text{K}$(G) denotes the set of all Hamiltonian circuits of G. Put H(n, r) = max{|E(G)|, |V(G)| = n, 1 ≤ |$\text{K}$(G)| ≤ r}. Theorem: $\text{H(n, 1) = (}\text{n}{}^2\text{2}\text{) + (}\text{n}\text{2}\text{) ?1}$. Further, H(n, 2),…, H(n, 5) are given.     

On a ramsey-type problem of J. A. Bondy and P. Erdös. I

Let m → (C_k, C_n) signify the truth of the following statement: Let {V(G); ≥ m; if G contains no C_k, then $\text{G}$ contains a C_n. Bondy and Erdös [1] proved that for n > 3 2n ? 1 → (C_n, C_n). They conjectured that 2n ? 1 → (C_n, C_k) for all n > 3 and all k < n and could prove it only for $\text{k < (2n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$. In this paper we prove this for all n > 4 and for all k < n.