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{?}$.     

A note on similar edges and edge-unique line graphs

If G is a connected graph having no vertices of degree 2 and L(G) is its line graph, two results are proven: if there exist distinct edges e and f with L(G) ? e ? L(G) ? f then there is an automorphism of L(G) mapping e to f; if $\text{G ? u ¦ G ? v}$ for any distinct vertices u, v, then $\text{L(G) ? e ¦ L(G) ? f}$ for any distinct edges e, f.     

Relative lengths of paths and cycles in k-connected graphs

Let G be a k-connected graph where k≥3. It is shown that if G contains a path L of length l then G also contains a cycle of length at least ($\text{(2k ? 4)}\text{(3k ? 4)}$) l. This result is obtained from a constructive proof that G contains 3k² ? 7k + 4 cycles which together cover every edge of L at least 2k² ? 6k + 4 times.     

Ordered colourings of graphs

An ordered colouring of a graph with k colours is a vertex colouring with colours {1, 2,…,k} such that each vertex coloured j is joined to at least one vertex-of colour i for each i less than j. Examples of ordered colourings are those produced by the greedy colouring algorithm. Some properties are investigated of τ(G), the maximum k for which the graph G has an ordered k-colouring (in fact τ(G) is an upper bound for the number of colours used by the greedy algorithm). It is shown that if G has order n, then $\text{τ(G) + τ(}\text{G}\text{) ≤ [}\text{(5n + 2)}\text{4}\text{]}$.     

Hamiltonian cycles in particular k-partite graphs

Let $\text{G}$(itk, p) denote the class of k-partite graphs, where each part is a stable set of cardinality p and where the edges between any pair of stable sets are those of a perfect matching. Maru?i? has conjectured that if G belongs to $\text{G}$(k, p) and is connected then G is hamiltonian. It is proved that the conjecture is true for k ≤ 3 or p ≤ 3; but for k ≥ 4 and p ≥ 4 a non-hamiltonian connected graph in $\text{G}$(k, p) is constructed.     

On graphs critical with respect to vertex partition numbers

For k?0, ?_k(G) denotes the Lick-White vertex partition number of G. A graph G is called (n, k)-critical if it is connected and for each edge e of G?_k(G–e)<?_k(G)=n. We describe all (2, k)-critical graphs and for n?3,k?1 we extend and simplify a result of Bollobás and Harary giving one construction of a family of (n, k)-critical graphs of every possible order.     

On a conjecture of bondy

Bondy conjectured [1] that: if G is a k-connected graph, where k ≥ 2, such that the degree-sum of any k + 1 independent vertices is at least m, then G contains a cycle of length at least: $\text{Min}\text{(}\text{2m}\text{(k + 1)}\text{, n)}$ (n denotes the order of G). We prove here that this result is true.     

On the sum of two sets in a group

Sums C = A + B of two finite sets in a (generally non-abelian) group are considered. The following two theorems are proved. 1. $\text{∣C∣ ≥ ∣A∣ +}\text{1}\text{2}\text{∣B∣}$ unless C + (?B + B) = C; 2. There is a subset S of C and a subgroup H such that ∣S∣ ≥ ∣A∣ + ∣B∣ ? ∣H∣, and either H + S = S or S + H = S.     

Minimum number of edges in graphs that are both P2- and Pi-connected

A simple graph with n vertices is called P_i-connected if any two distinct vertices are connected by an elementary path of length i. In this paper, lower bounds of the number of edges in graphs that are both P₂- and P_i-connected are obtained. Namely if $\text{i?}\text{1}\text{2}\text{(n+1)}$, then |E(G)|?((4i?5)/(2i?2))(n?1), and if $\text{i >}\text{1}\text{2}\text{(n+ 1)}$, then |E(G)|?2(n?1) apart from one exeptional graph. Furthermore, extremal graphs are determined in the former.     

On the dimension of trees

It is proved that for trees (and forests) G one has dimG?3 log⁺₂∣G∣(where dim G, the dimension of G, is the minimum k such that G is embeddable into a product of k complete graphs; ∣G∣ is the size of G). Moreover, if m(G) is the quotient of G obtained by identifying the points with coinciding neighbour sets, one has, for forests G, log⁺₂ ∣m(G)∣ ? 1 ? dimG ? 3 log⁺₂m(G>) + 1. Also, for the bipartite dimension bid G (arising from embeddings into P^k₃) one has bid G ? 8 log⁺₂ ∣G ∣.     

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.     

Edge-choosability of planar graphs without adjacent triangles or without 7-cycles

A graph G is edge-L-colorable, if for a given edge assignment L={L(e):e∈E(G)}, there exists a proper edge-coloring ? of G such that ?(e)∈L(e) for all e∈E(G). If G is edge-L-colorable for every edge assignment L with |L(e)|≥k for e∈E(G), then G is said to be edge-k-choosable. In this paper, we prove that if G is a planar graph with maximum degree Δ(G)≠5 and without adjacent 3-cycles, or with maximum degree Δ(G)≠5,6 and without 7-cycles, then G is edge-(Δ(G)+1)-choosable.     

Adjacent strong edge coloring of graphs

For a graph G(V, E), if a proper k-edge coloring ƒ is satisfied with C(u) ≠ C(v) for uv ∈ E(G), where $\text{C(u) = {ƒ(uv) | uv ∈ E}}$, then ƒ is called k-adjacent strong edge coloring of G, is abbreviated k-ASEC, and χ′_as(G) = min{k | k-ASEC of G} is called the adjacent strong edge chromatic number of G. In this paper, we discuss some properties of χ′_as(G), and obtain the χ′_as(G) of some special graphs and present a conjecture: if G are graphs whose order of each component is at least six, then χ′_as(G) ≤ Δ(G) + 2, where Δ(G) is the maximum degree of G.     

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.     

On complementary graphs with no isolated vertices

Let $\text{G}$ denote the complement of a graph G, and x(G), β₁(G), β₄(G), α₀(G), α₁(G) denote respectively the chromatic number, line-independence number, point-independence number, point-covering number, line-covering number of G, Nordhaus and Gaddum showed that for any graph G of order $\text{p}\text{, {2√p} ? x(G) + x(}\text{G}\text{) ? p + 1}\text{and p}\text{? x(G)·x(}\text{G}\text{) ? [(}\text{1}\text{2}\text{(p + 1))}{}^2\text{]}$. Recently Chartrand and Schuster have given the corresponding inequalities for the independence numbers of any graph G. However, combining their result with Gallai's well known formula β₁(G) + α₁(G) = ?, one is not deduce the analogous bounds for the line-covering numbers of $\text{G}\text{and}\text{G}$, since Gallai's formula holds only if G contains no isolated vertex. The purpose of this note is to improve the results of Chartland and Schuster for line-independence numbers for graphs where both $\text{G}\text{and}\text{G}$ contain no isolated vertices and thereby allowing us to use Gallai's formula to get the corresponding bounds for the line-covering numbers of G.     

On total matching numbers and total covering numbers of complementary graphs

Best upper and lower bounds, as functions of n, are obtained for the quantities $\text{β}{}_2\text{(G)+β}{}_2\text{(}\text{G}\text{?}\text{)}$ and $\text{α}{}_2\text{(G)+α}{}_2\text{(}\text{G}\text{?}\text{)}$, where β₂(G) denotes the total matching number and α₂(G) the total covering number of any graph G with n vertices and with complementry graph ?.The best upper bound is obtained also for α₂(G)+β₂(G), when G is a connected graph.     

Omega theorems for the iterated additive convolution of a nonnegative arithmetic function

Let R_k(n) denote the number of ways of representing the integers not exceeding n as the sum of k members of a given sequence of nonnegative integers. Suppose that $\text{1}\text{2}\text{< β < k}$, $\text{δ =}\text{β}\text{2}\text{?}\text{β}\text{(4}\text{min}\text{(β,}\text{k}\text{2}\text{))}$ and

$\text{ξ=}\text{1/2β if β<k/2,}\text{β?1/2 if β=1/2,}\text{(k ? 2)(k + 1)/2k if k/2<β<k.}$

R. C. Vaughan has shown that the relation R_k(n) = G(n) + o(n^δ log^?ξn) as n → +∞ is impossible when G(n) is a linear combination of powers of n and the dominant term of G(n) is cn^β, c > 0. P. T. Bateman, for the case k = 2, has shown that similar results can be obtained when G(n) is a convex or concave function. In this paper, we combine the ideas of Vaughan and Bateman to extend the theorems stated above to functions whose fractional differences are of one sign for large n. Vaughan's theorem is included in ours, and in the case $\text{β <}\text{k}\text{2}$ we show that a better choice of parameter improves Vaughan's result by enabling us to drop the power of log n from the estimate of the error term.     

Solving NP-hard problems in ‘almost trees’: Vertex cover

We present an algorithm which finds a minimum vertex cover in a graph G(V, E) in time $\text{O}\text{(|V|+(}\text{a}\text{k}\text{)2}{}^{\mathrm{<mtext>k</mtext><mtext>3</mtext>}}\text{)}$, where for connected graphs G the parameter a is defined as the minimum number of edges that must be added to a tree to produce G, and k is the maximum a over all biconnected components of the graph. The algorithm combines two main approaches for coping with NP-completeness, and thereby achieves better running time than algorithms using only one of these approaches.