Complexity of representation of graphs by set systems

Let $\text{F}$ be a family of subsets of S and let G be a graph with vertex set $\text{V={x}{}_{\mathrm{A}}\text{|A ∈}\text{F}\text{}}$ such that: (x_A, x_B) is an edge iff $\text{A?B≠}\text{0}\text{/}$. The family $\text{F}$ is called a set representation of the graph G.It is proved that the problem of finding minimum k such that G can be represented by a family of sets of cardinality at most k is NP-complete. Moreover, it is NP-complete to decide whether a graph can be represented by a family of distinct 3-element sets.The set representations of random graphs are also considered.     

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

Spanning subgraphs of k-connected digraphs

It is shown that every k-edge-connected digraph with m edges and n vertices contains a spanning connected subgraph having at most $\text{2m + 6(k ?1)(n ? 1))}\text{(5k ? 3)}$ edges. When k = 2 the bound is improved to $\text{(3m + 8(n ? 1))}\text{10}$, which implies that a 2-edge-connected digraph is connected by less than 70% of its edges. Examples are given which require almost two-thirds of the edges to connect all vertices.     

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.     

Forbidding just one intersection

Following a conjecture of P. Erdös, we show that if $\text{F}$ is a family of k-subsets of and n-set no two of which intersect in exactly l elements then for k ? 2l + 2 and n sufficiently large |$\text{F}$| ? (_{k ? l ? 1}^{n ? l ? 1}) with equality holding if and only if $\text{F}$ consists of all the k-sets containing a fixed (l + 1)-set. In general we show |$\text{F}$| ? d_kn^{max;{;l,k ? l ? 1};}, where d_k is a constant depending only on k. These results are special cases of more general theorems (Theorem 2.1–2.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.     

The diameter of bipartite distance-regular graphs

It is shown that any bipartite distance-regular graph with finite valency k and at least one cycle is finite, with diameter d and girth g satisfying $\text{d≤}\text{(k?1)(g?2)}\text{2+1}$. In particular, the number of bipartite distance-regular graphs with fixed valency and girth is finite.     

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 existence of uncountably many matroidal families

A matroidal family is a set $\text{F}$ ≠ ? 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{F}$ are the circuits of a matroid on the edge-set of G. Simões-Pereira [5] shows the existence of four matroidal families and Andreae [1] shows the existence of a countably infinite series of matroidal families. In this paper we show that there exist uncountably many matroidal families. This is done by using an extension of Andreae's theorem, a construction theorem, and certain properties of regular graphs. Moreover we observe that all matroidal families so far known can be obtained in a unified way.     

Nowhere-zero 3-flows and modulo k-orientations

The main theorem of this paper provides partial results on some major open problems in graph theory, such as Tutte?s 3-flow conjecture (from the 1970s) that every 4-edge connected graph admits a nowhere-zero 3-flow, the conjecture of Jaeger, Linial, Payan and Tarsi (1992) that every 5-edge-connected graph is _Z3$Z_3$-connected, Jaeger?s circular flow conjecture (1984) that for every odd natural number k?3$k?3$, every (2k−2)$(2k-2)$-edge-connected graph has a modulo k  -orientation, etc. It was proved recently by Thomassen that, for every odd number k?3$k?3$, every (2k²+k)$(2k^2+k)$-edge-connected graph G has a modulo k-orientation; and every 8-edge-connected graph G   is _Z3$Z_3$-connected and admits therefore a nowhere-zero 3-flow. In the present paper, Thomassen?s method is refined to prove the following: For every odd number  k?3$k?3$, every  (3k−3)$(3k-3)$-edge-connected graph has a modulo k-orientation. As a special case of the main result, every 6-edge-connected graph is  _Z3$Z_3$-connected and admits therefore a nowhere-zero 3-flow. Note that it was proved by Kochol (2001) that it suffices to prove the 3-flow conjecture for 5-edge-connected graphs.     

k-Blocks and ultrablocks in graphs

A k-block is a maximal k-vertex-connected subgraph, and a k-block which does not contain a (k + 1)-block is an ultrablock. It is shown that the maximum total number of k-blocks for all k ≥ 1 in any p-vertex graph is [$\text{(2p ? 1)}\text{3}$], and the maximum number of ultrablocks in any p-vertex graph having maximum subgraph connectivity κ? is $\text{[}\text{(p ?}\text{κ}\text{?}\text{+ 1)}\text{2}\text{]}$. In contrast to the linear growth rate of the maximum number of k-blocks in a p-vertex graph, it is shown that the maximum number of critical k-vertex-connected subgraphs of an ultrablock of connectivity k can grow exponentially with p.     

The validity of the strong perfect-graph conjecture for (K4−e)-free graphs

Berge's strong perfect-graph conjecture states that a graph is perfect iff it has neither C_2n+1 nor $\text{C}{}_{\mathrm{2n+1}}$, n ≥ 2 as an induced subgraph. In this note we establish the validity of this conjecture for (K₄?e)-free graphs.     

Eigenvalue multiplicities of highly symmetric graphs

We find lower bounds on eigenvalue multiplicities for highly symmetric graphs. In particular we prove:Theorem 1. If Γ is distance-regular with valency k and girth g (g?4), and λ (λ≠±?k) is an eigenvalue of Γ, then the multiplicity of λ is at least

$\text{k(k?1)}{}^{\mathrm{<mtext>[</mtext><mtext>g</mtext><mtext>4</mtext><mtext>]?1</mtext>}}$

if g≡0 or 1 (mod 4),

$\text{2(k?1)}{}^{\mathrm{<mtext>[</mtext><mtext>g</mtext><mtext>4</mtext><mtext>]</mtext>}}$

if g≡2 or 3 (mod 4) where [ ] denotes integer part. Theorem 2. If the automorphism group of a regular graph Γ with girth g (g?4) and valency k acts transitively on s-arcs for some s, $\text{1?s?[}\text{1}\text{2}\text{g]}$, then the multiplicity of any eigenvalue λ (λ≠±?k) is at least

$\text{k(k?1)}{}^{\mathrm{<mtext>s</mtext><mtext>2?1</mtext>}}$

if s is even,

$\text{2(k?1)}{}^{\mathrm{<mtext>(</mtext><mtext>s?1)</mtext><mtext>2</mtext>}}$

if s is odd.     

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.     

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.     

Antipodal graphs of diameter three

Distance-regular graphs of diameter three are of three (almost distinct) kinds: primitive, bipartite, and antipodal. An antipodal graph of diameter three is just an r-fold covering of a complete graph K_k+1 for some r?k. Its intersection array and spectrum are determined by the parameters r, k together with the number c of 2-arcs joining any two vertices at distance two. Most such graphs have girth three. In this note we consider antipodal distance-regular graphs of diameter three and girth ? 4. If r=2, then the only graphs are “K_{k+1, k+1} minus a 1-factor.” We therefore assume r?3. The graphs with c=1 necessarily have r=k and were classified in lsqb3rsqb. We prove the inequality $\text{r?2>c}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ (Theorem 2), list the feasible parameter sets when c=2 or 3 (Corollary 1), and conclude that every 3-fold or 4-fold antipodal covering of a complete graph has girth three (Corollary 2).     

Unavoidable stars in 3-graphs

Suppose $\text{F}$ is a collection of 3-subsets of {1,2,…,n}. The problem of determining the least integer $\text{?(n, k)}$ with the property that if $\text{|F| > ?(n, k)}$ then $\text{F}$ contains a k-star (i.e., k 3-sets such that the intersection of any pair of them consists of exactly the same element) is studied. It is proved that, for k odd, $\text{?(n, k) = k(k ? 1)n + O(k}{}^3\text{)}$ and, for k even, $\text{?(n, k) = k(k ?}\text{3}\text{2}\text{)n + O(n + k}{}^3\text{)}$.     

On multiply critically h-connected graphs

A conjecture of Slater states that K_{h + 1} is the unique k-critically h-connected noncomplete graph for 2k > h. We prove here that there is no k-critically h-connected connected graph with order $\text{?h + k ? 2}\text{for}\text{2k > h + 1}$. We prove also that there is no k-critically h-connected line graph for 2k > h. The last result was conjectured by Maurer and Slater. We apply in our proofs a method introduced by Mader.     

The extremal graph problem of the icosahedron

P. Turán has asked the following question:Let I¹² be the graph determined by the vertices and edges of an icosahedron. What is the maximum number of edges of a graph Gⁿ of n vertices if Gⁿ does not contain I¹² as a subgraph?We shall answer this question by proving that if n is sufficiently large, then there exists only one graph having maximum number of edges among the graphs of n vertices and not containing I¹². This graph Hⁿ can be defined in the following way:Let us divide n ? 2 vertices into 3 classes each of which contains [$\text{(n?2)}\text{3}$] or $\text{[}\text{(n?2)}\text{3}\text{] + 1}$ vertices. Join two vertices iff they are in different classes. Join two vertices outside of these classes to each other and to every vertex of these three classes.