On -factors in the cube of a graph
On 1-dependent ramsey numbers for graphs
A set X of vertices of a graph G is said to be 1-dependent if the subgraph of G induced by X has maximum degree one. The 1-dependent Ramsey number t₁(l,m) is the smallest integer n such that for any 2-edge colouring (R,B) of Kₙ, the spanning subgraph B of Kₙ has a 1-dependent set of size l or the subgraph R has a 1-dependent set of size m. The 2-edge colouring (R,B) is a t₁(l,m) Ramsey colouring of Kₙ if B (R, respectively) does not contain a 1-dependent set of size l (m, respectively); in this...
On 1-Factorability and Edge-Colorability of Cartesian Products of Graphs.
On -extendability of generalized Petersen graphs
Let be a generalized Petersen graph with , Then every pair of parallel edges of is contained in a 1-factor of . This partially answers a question posed by Larry Cammack and Gerald Schrag [Problem 101, Discrete Math. 73(3), 1989, 311-312].
On 2-cell embeddings of graphs with minimum numbers of regions
On 2-cell imbeddings of complete n-partite graphs
On 2-factors in squares of graphs
On 2-periodic graphs of a certain graph operator
We deal with the graph operator defined to be the complement of the square of a graph: . Motivated by one of many open problems formulated in [6] we look for graphs that are 2-periodic with respect to this operator. We describe a class of bipartite graphs possessing the above mentioned property and prove that for any m,n ≥ 6, the complete bipartite graph can be decomposed in two edge-disjoint factors from . We further show that all the incidence graphs of Desarguesian finite projective geometries...
On 3-simplicial vertices in planar graphs
A vertex v in a graph G = (V,E) is k-simplicial if the neighborhood N(v) of v can be vertex-covered by k or fewer complete graphs. The main result of the paper states that a planar graph of order at least four has at least four 3-simplicial vertices of degree at most five. This result is a strengthening of the classical corollary of Euler's Formula that a planar graph of order at least four contains at least four vertices of degree at most five.
On -choosability of toroidal graphs without chordal 7-cycles and adjacent 4-cycles
A graph is called -choosable if for every list assignment satisfying for all , there is an -coloring of such that each vertex of has at most neighbors colored with the same color as itself. In this paper, it is proved that every toroidal graph without chordal 7-cycles and adjacent 4-cycles is -choosable.
On (4, 2)-digraphs containing a cycle of length 2.
On -connected, planar -almost pancyclic graphs
On a -factor of the fourth power of a connected graph
On a bound on algebraic connectivity: the case of equality
In a recent paper the authors proposed a lower bound on , where , , is an eigenvalue of a transition matrix of an ergodic Markov chain. The bound, which involved the group inverse of , was derived from a more general bound, due to Bauer, Deutsch, and Stoer, on the eigenvalues of a stochastic matrix other than its constant row sum. Here we adapt the bound to give a lower bound on the algebraic connectivity of an undirected graph, but principally consider the case of equality in the bound when...
On a certain class of multidigraphs, for which reversal of no arc decreases the number of their cycles
On a certain class of polytopes associated with independence systems.
On a certain distance between isomorphism classes of graphs
On a certain homomorphism properties of graphs II.
On a certain numbering of the vertices of a hypergraph
On a certain ordering of the vertices of a tree