Cycle covering in bridgeless graphs

We prove that any bridgeless graph G = (V, E), |E| = m, |V| = N, admits a cycle cover of total length at most $\text{m +}\text{5}\text{4}\text{(n ? 1)}$. We give a quick survey of the related problems and establish some properties for the vertex covering problem and for shortest coverings of cographic matroids.     

An extension of Tutte's 1-factor theorem

We prove the following theorem: Let G be a graph with vertex-set V and ?, g be two integer-valued functions defined on V such that $\text{0}\text{?g(x) ?1??(x)}$ for all x ∈ V. Then G contains a factor F such that $\text{g(x)?d}{}_{\mathrm{F}}\text{(x)??(x)}$ for all x ∈ V if and only if for every subset X of V, $\text{?(X)}$ is at least equal to the number of connected components C of G[V ? X] such that either C = {x} and g(x) = 1, or |C| is odd ?3 and $\text{g(x) = ?(x) =}\text{1}$ for all x ∈ C. Applications are given to certain combinatorial geometries associated with factors of graphs.     

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.     

The 7/5-conjecture strengthens itself

The following is proved: if every bridgeless graph G has a cycle cover of length at most 7/5|E(G)|, then every bridgeless graph G has a cycle cover of length at most 7/5|E(G)| such that any edge of G is covered once or twice. © 1995 John Wiley & Sons, Inc.     

On a general class of graph polynomials

Let $\text{F}$ be a family of connected graphs. With each element α ∈ $\text{F}$, we can associate a weight w_α. Let G be a graph. An F-cover of G is a spanning subgraph of G in which every component belongs to $\text{F}$. With every F-cover we can associate a monomial π(C) = Π_αw_α, where the product is taken over all components of the cover. The F-polynomial of G is Σπ(C), where the sum is taken over all F-covers in G. We obtain general results for the complete graph and complete bipartite graphs, and we show that many of the well-known graph polynomials are special cases of more general F-polynomials.     

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.     

A sufficient condition for hamiltonian circuits

A theorem is proved that is (in a sense) the best possible improvement on the following theme: If G is an undirected graph on n vertices in which $\text{|Γ(S)| ≥}\text{1}\text{3}\text{(n + | S | + 3)}$ for every non-empty subset S of the vertices of G, then G is Hamiltonian.     

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.     

Finding minimum dominating cycles in permutation graphs

A dominating cycle for a graph G = (V, E) is a subset C of V which has the following properties: (i) the subgraph of G induced by C has a Hamiltonian cycle, and (ii) every vertex of V is adjacent to some vertex of C. In this paper, we develop an O(n²) algorithm for finding a minimum cardinality dominating cycle in a permutation graph. We also show that a minimum cardinality dominating cycle in a permutation graph always has an even number of vertices unless it is isomorphic to C₃.     

Minimal triangulation of a graph and optimal pivoting order in a sparse matrix

This paper considers the problem of finding a minimal triangulation of an undirected graph G = (V, E), where a triangulation is a set T such that every cycle in G = (V, E ∪ T) has a chord. A triangulation T is minimal (minimum) if no triangulation F exists such that F is a proper subset of $\text{T (¦F¦ < ¦T¦)}$, and an ordering α is optimal (optimum) if a minimal (minimum) triangulation is generated by α. A minimum triangulation (optimum ordering) is necessarily minimal (optimal), but the converse is not necessarily true. A necessary and sufficient condition for a triangulation to be minimal is presented. This leads to an algorithm for finding an optimal ordering α which produces a minimal set of “fill-in” when the process is viewed as triangular factorization of a sparse matrix.     

The binding number of a graph and its Anderson number

The binding number of a graph G, bind(G), is defined; some examples of its calculation are given, and some upper bounds for it are proved. It is then proved that, if bind(G) ≥ c, then G contains at least $\text{|G|}\text{c}\text{(c + 1)}$ disjoint edges if $\text{0 ≤ c ≤}\text{1}\text{2}$, at least $\text{| G |}\text{(3c ? 2)}\text{3c}\text{?}\text{2(c ? 1)}\text{c}$ disjoint edges if $\text{1 ≤ c ≤}\text{4}\text{3}$, a Hamiltonian circuit if $\text{c ≥}\text{3}\text{2}$, and a circuit of length at least $\text{3(| G | ?1)(c ? 1)}\text{c}$ if $\text{1 < c ≤}\text{3}\text{2}$ and G is not one of two specified exceptional graphs. Each of these results is best possible.The Anderson number of a graph is defined. The Anderson numbers of a few very simple graphs are determined; and some rather weak bounds are obtained, and some conjectures made, on the Anderson numbers of graphs in general.     

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.     

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.     

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.     

A degree sum condition for long cycles passing through a linear forest

Let G be a (k+m)-connected graph and F be a linear forest in G such that |E(F)|=m and F has at most k-2 components of order 1, where k?2 and m?0. In this paper, we prove that if every independent set S of G with |S|=k+1 contains two vertices whose degree sum is at least d, then G has a cycle C of length at least min{d-m,|V(G)|} which contains all the vertices and edges of F.     

Infinite subgraphs as matroid circuits

A matroidal family $\text{C}$ is defined to be a collection of graphs such that, for any given graph G, the subgraphs of G isomorphic to a graph in $\text{C}$ satisfy the matroid circuit-axioms. Here matroidal families closed under homeomorphism are considered. A theorem of Simöes-Pereira shows that when only finite connected graphs are allowed as members of $\text{C}$, two matroids arise: the cycle matroid and bicircular matroid. Here this theorem is generalized in two directions: the graphs are allowed to be infinite, and they are allowed to be disconnected. In the first case four structures result and in the second case two infinite families of matroids are obtained. The main theorem concerns the structures resulting when both restrictions are relaxed simultaneously.     

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.