Abstract:
We give a simple proof of Tutte's theorem stating that the cycle space of a 3--connected graph is generated by the set of non-separating circuits of the graph. Keywords: graph, cycle, circuit, cycle space, non-separating circuit, strong isomorphism.

Abstract:
An L-factor of a graph G is a spanning subgraph of G whose every component is a 3-vertex path. Let v(G) denote the number of vertices of G. A graph is called claw-free if it does not have a subgraph isomorphic to the graph with 4 vertices and 3 edges having a common vertex. Our results include the following. Let G$ be a 3-connected claw-free graph, x be a vertex, e = xy be an edge, and P be a 3-vertex path in G. Then (c1) if v(G) = 0 mod 3, then G has an L-factor containing (avoiding) e, (c2) if v(G) = 1 mod 3, then G - x has a L-factor, (c3) if v(G) = 2 mod 3, then G - x -y has an L-factor, (c4) if v(G) = 0 mod 3 and G is either cubic or 4-connected, then G - P has an L-factor, and (c5) if G is cubic and E is a set of three edges in G, then G - E has an L -factor if and only if the subgraph induced by E in G is not a claw and not a triangle. Keywords: claw-free graph, cubic graph, L-packing, L-factor.

Abstract:
We give a construction that provides infinitely many 2-connected, cubic, bipartite, and planar graphs G with 3k vertices and such that the number of disjoint copies of a 3-vertex path in G is less than k.

Abstract:
Let v(G) and p(G) be the number of vertices and the maximum number of disjoint 3-vertex paths in G, respectively. We discuss the following old Problem: Is the following claim (P) true ? (P) if G is a 3-connected and cubic graph, then p(G) = [v(G)/3], where [v(G)/3] is the floor of v(G)/3. We show, in particular, that claim (P) is equivalent to some seemingly stronger claims. It follows that if claim (P) is true, then Reed's dominating graph conjecture (see [14]) is true for cubic 3-connected graphs.

Abstract:
We give a simple proof of MacLane's algebraic planarity criterion for graphs. This proof does not use any other known planarity criteria. Keywords: graph, planarity, cycle space, a simple basis of a graph.

Abstract:
Let v(G) and dom(G) denote the number of vertices and the domination number of a graph G, and let r (G) = dom(G)/v(G)$. Let [x] and ]x[ be the floor and the ceiling of a number x. In 1996 B. Reed conjectured that if G is a cubic graph, then dom(G) is at most ]v(G)/3[. In 2005 A. Kostochka and B. Stodolsky disproved this conjecture for cubic graphs of connectivity one and maintained that the conjecture may still be true for 2-connected cubic graphs. Their minimum counterexample C has 4 bridges, v(C) = 60, anddom (C) = 21. In this paper we disprove Reed's conjecture for 2-connected cubic graphs by providing a sequence (R(k): k > 2) of cubic graphs of connectivity two with r(R_k) = 1/3 + 1/60, where v(R(k+1)) > v(R(k)) > v(R(3)) = 60 for k > 3, and so dom(R(3)) = 21$ and dom(R(k)) - ]v(R(k))/3[ tends to infinity when k tends to infinity. We also provide a sequence of (L_s: s > 0) of cubic graphs of connectivity one with r(L(s)) > 1/3 + 1/60. The minimum counterexample L = L(1) in this sequence is `better' than C in the sense that L has 2 bridges while C has 4 bridges, v(L) = 54 < 60 = v(C), and r(L) = 1/3 + 1/54} > 1/3 + 1/60 = r(C). We also give a construction providing for every t in {0,1,2} infinitely many cubic cyclically 4-connected Hamiltonian graphs G(t) such that v(G(t)) = t mod 3, t in {0,2} implies dom(G(t)) = ]v(G(r))/3[, and t = 1 implies dom(G(t)) = [v(G(r))/3]. At last we suggest a stronger conjecture on domination in cubic 3-connected graphs.

Abstract:
Let v(G) be the number of vertices and t(G,k) the maximum number of disjoint k-edge trees in G. In this paper we show that (a1) if G is a graph with every vertex of degree at least two and at most s, where s > 3, then t(G,2) is at least v(G)/(s+1), (a2) if G is a graph with every vertex of degree at least two and at most 3 and G has no 5-vertex components, then t(G,2) is at least v(G)/4, (a3) if G is a graph with every vertex of degree at least one and at most s and G has no k--vertex component, where k >1 and s > 2, then t(G,k) is at least (v(G) - k)/(sk - k +1), and (a4) the above bounds are attained for infinitely many connected graphs. Our proofs provide polynomial time algorithms for finding the corresponding packings in a graph. Keywords: subgraph packing, 2-edge and k-edge paths, k-edge trees, polynomial time approximation algorithms.

Abstract:
An st-path is a path with the end-vertices s and t. An s-path is a path with an end-vertex s. The results of this paper include necessary and sufficient conditions for a {claw, net}-free graph G with given two different vertices s, t and an edge e to have (1)a Hamiltonian s-path, (2) a Hamiltonian st-path, (3) a Hamiltonian s- and st-paths containing edge e when G has connectivity one, and (4) a Hamiltonian cycle containing e when G is 2-connected. These results imply that a connected {claw, net}-free graph has a Hamiltonian path and a 2-connected {claw, net}-free graph has a Hamiltonian cycle [D. Duffus, R.J. Gould, M.S. Jacobson, Forbidden Subgraphs and the Hamiltonian Theme, in The Theory and Application of Graphs (Kalamazoo, Mich., 1980$), Wiley, New York (1981) 297--316.] Our proofs of (1)-(4) are shorter than the proofs of their corollaries in [D. Duffus, R.J. Gould, M.S. Jacobson] and provide polynomial-time algorithms for solving the corresponding Hamiltonicity problems. Keywords: graph, claw, net, {claw, net}-free graph, Hamiltonian path, Hamiltonian cycle, polynomial-time algorithm.

Abstract:
A subgraph (a spanning subgraph) of a graph G whose all components are 3-vertex paths is called an L-packing (respectively, an L-factor} of G. We discuss the following old PROBLEM (A. Kelmans, 1984). Is the following claim true? (C) If G is a cubic 3-connected graph, then G has an L-packing that avoids at most two vertices of G. We show, in particular, that claim (C) is equivalent to some seemingly stronger claims (see Theorem 3.1 below). For example, if G is a cubic 3-connected graph and the number of vertices of G is divisible by three, then then the following claims are equivalent: G has an L-factor, for every edge e of G there is an L-factor of G avoiding (containing) e, G - {e,f} has an L-factor for every two edges e and f of G, and G - P has an L-factor for every 3-vertex path P in G. It follows that if claim (C) is true, then Reed's dominating graph conjecture is true for cubic 3-connected graphs. We also show that certain claims in Theorem 3.1 are best possible. We give a construction providing infinitely many cyclically 6-connected graphs G with two disjoint 3-vertex paths P and P' such that the number of vertices of G is divisible by three and G - P- P' has no L-factor. Keywords: cubic 3-connected graph, 3-vertex path packing, 3-vertex path factor, domination.

Abstract:
In this partly expository paper we discuss and describe some of our old and recent results on partial orders on the set (m,n)-graphs (i.e. graphs with n vertices and m edges) and some operations on graphs that are monotone with respect to these partial orders. The partial orders under consideration include those related with some Laplacian characteristics of graphs as well as with some probabilistic characteristics of graphs with randomly deleted edges. Section 2 provides some notions, notation, and simple observations. Section 3 contains some basic facts on the Laplacian polynomial of a graph. Section 4 describes various graph operation and their properties. In Section 5 we introduce some partial orders on the set of (m,n)-graphs related, in particular, with the graph Laplacian and the graph reliability (Laplacian posets and reliability posets}). Section 6 contains some old and recent results on the monotonicity of some graph operations with respect to Laplacian posets. Section 7 and 8 include some old and recent results on the monotonicity of some graph operations with respect to reliability posets and to some other parameters of graphs as well as some open problems. Section 9 contains some generalizations of the described results on weighted graphs. Keywords: graph, graph operations, graph posets, random graphs, decomposable graphs, threshold graphs, weighted graphs, spanning subgraphs, Laplacian polynomial and spectrum, adjacency polynomial and spectrum, graph reliability, trees, forests, Hamiltonian cycle and path, symmetric polynomials