Three-linking in Eulerian digraphs
A graph is called -free if contains no induced subgraph isomorphic to any graph , . We define In this paper, we prove that (1) if is a connected -free graph of order and , then is traceable, (2) if is a 2-connected -free graph of order and for any two distinct pairs of non-adjacent vertices , of , then is traceable, i.e., has a Hamilton path, where is a graph obtained by joining a pair of non-adjacent vertices in a .
In a bidirected graph, an edge has a direction at each end, so bidirected graphs generalize directed graphs. We generalize the definitions of transitive closure and transitive reduction from directed graphs to bidirected graphs by introducing new notions of bipath and bicircuit that generalize directed paths and cycles. We show how transitive reduction is related to transitive closure and to the matroids of the signed graph corresponding to the bidirected graph.
In this paper, by a travel groupoid is meant an ordered pair such that is a nonempty set and is a binary operation on satisfying the following two conditions for all : Let be a travel groupoid. It is easy to show that if , then if and only if . We say that is on a (finite or infinite) graph if and Clearly, every travel groupoid is on exactly one graph. In this paper, some properties of travel groupoids on graphs are studied.
An eigenvalue of a graph G is called a main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero. Let G 0 be the graph obtained from G by deleting all pendant vertices and δ(G) the minimum degree of vertices of G. In this paper, all connected tricyclic graphs G with δ(G 0) ≥ 2 and exactly two main eigenvalues are determined.
Let be a graph. Gould and Hynds (1999) showed a well-known characterization of by its line graph that has a 2-factor. In this paper, by defining two operations, we present a characterization for a graph to have a 2-factor in its line graph A graph is called -locally connected if for every vertex
The oriented chromatic number of an oriented graph is the minimum order of an oriented graph such that admits a homomorphism to . The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations. In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph G, defined as the minimum order of an oriented graph such that every orientation of G admits a homomorphism to . We give some properties...
Given a 2-connected graph G on n vertices, let G* be its partially square graph, obtained by adding edges uv whenever the vertices u,v have a common neighbor x satisfying the condition , where . In particular, this condition is satisfied if x does not center a claw (an induced ). Clearly G ⊆ G* ⊆ G², where G² is the square of G. For any independent triple X = x,y,z we define σ̅(X) = d(x) + d(y) + d(z) - |N(x) ∩ N(y) ∩ N(z)|. Flandrin et al. proved that a 2-connected graph G is hamiltonian if...
Given a coloring of the vertices of a graph G, we say a subgraph is rainbow if its vertices receive distinct colors. For a graph F, we define the F-upper chromatic number of G as the maximum number of colors that can be used to color the vertices of G such that there is no rainbow copy of F. We present some results on this parameter for certain graph classes. The focus is on the case that F is a star or triangle. For example, we show that the K3-upper chromatic number of any maximal outerplanar...
Let G be a graph of order n. Let K¯ₗ be the graph obtained from Kₗ by removing one edge. In this paper, we propose the following conjecture: Let G be a graph of order n ≥ lk with δ(G) ≥ (n-k+1)(l-3)/(l-2)+k-1. Then G has k vertex-disjoint K¯ₗ. This conjecture is motivated by Hajnal and Szemerédi's [6] famous theorem. In this paper, we verify this conjecture for l=4.
A cycle C is a vertex-dominating cycle if every vertex is adjacent to some vertex of C. Bondy and Fan [4] showed that if G is a 2-connected graph with δ(G) ≥ 1/3(|V(G)| - 4), then G has a vertex-dominating cycle. In this paper, we prove that if G is a 2-connected bipartite graph with partite sets V₁ and V₂ such that δ(G) ≥ 1/3(max{|V₁|,|V₂|} + 1), then G has a vertex-dominating cycle.