Search

Let H be a set of graphs. A graph G is said to be H -free if G does not contain H as an induced subgraph for all H ∈ H , and we call H a forbidden pair if | H | = 2. A graph is called supereulerian if it contains a spanning connected even subgraph. In 1979, Pulleyblank showed that determining whether a graph is supereulerian, even when restricted to planar graphs, is NP-complete. In this paper, we characterize all pairs of graphs R , S (not necessary connected) such that every 2-connected or 2-edge-connected { R , S } -free graph (of sufficiently large order) is supereulerian. We also characterize all minimal 2-connected non-supereulerian graphs, which extends a result by the third author and Xiong (2017) [29]. [ABSTRACT FROM AUTHOR]

Let H be a class of given graphs. A graph G is said to be H -free if G contains no induced copies of H for every H ∈ H . A graph is called traceable if it contains a Hamilton path. Faudree and Gould (1997) characterized all the pairs { R , S } of connected subgraphs such that every connected { R , S } -free graph is traceable. Li and Vrána (2016) first consider the disconnected forbidden subgraphs, and characterized all pairs of disconnected forbidden subgraphs for hamiltonicity. In this article, we characterize all pairs { R , S } of graphs such that there exists an integer n 0 such that every connected { R , S } -free graph of order at least n 0 is traceable. [ABSTRACT FROM AUTHOR]

Let H be a given graph. A graph G is said to be H-free if G contains no induced copies of H. For a class [ABSTRACT FROM AUTHOR]

In this paper, we consider the least integer d such that every longest cycle of a k-connected graph of order n (and of independent number α) contains all vertices of degree at least d. [ABSTRACT FROM AUTHOR]

Let $$G$$ be a $$k$$ -connected graph with $$k\ge 2$$ . In this paper we first prove that: For two distinct vertices $$x$$ and $$z$$ in $$G$$ , it contains a path connecting $$x$$ and $$z$$ which passes through its any $$k-2$$ specified vertices with length at least the average degree of the vertices other than $$x$$ and $$z$$ . Further, with this result, we prove that: If $$G$$ has $$n$$ vertices and $$m$$ edges, then it contains a cycle of length at least $$2m/(n-1)$$ passing through its any $$k-1$$ specified vertices. Our results generalize a theorem of Fan on the existence of long paths and a classical theorem of Erdős and Gallai on the existence of long cycles under the average degree condition. [ABSTRACT FROM AUTHOR]

Abstract: Bollobás and Scott proved that if the weighted outdegree of every vertex of an edge-weighted digraph is at least 1, then the digraph contains a (directed) path of weight at least 1. In this note we characterize the extremal weighted digraphs with no heavy paths. Our result extends a corresponding theorem of Bondy and Fan on weighted graphs. We also give examples to show that a result of Bondy and Fan on the existence of heavy paths connecting two given vertices in a 2-connected weighted graph does not extend to 2-connected weighted digraphs. [Copyright &y& Elsevier]

An arc u v of a digraph D is called universal if u v and w are in a common cycle for any vertex w of D . We show that every arc of a tournament T is universal if and only if T is either 2-connected or has a cut-vertex v such that the in- and out-neighbors of v both induce strongly connected subtournaments. [ABSTRACT FROM AUTHOR]

The 1–2–3 Conjecture asserts that, for every connected graph different from K 2 , its edges can be labeled with 1 , 2 , 3 so that, when coloring each vertex with the sum of its incident labels, no two adjacent vertices get the same color. This conjecture takes place in the more general context of distinguishing labelings, where the goal is to label graphs so that some pairs of their elements are distinguishable relatively to some parameter computed from the labeling. In this work, we investigate the consequences of labeling graphs as in the 1–2–3 Conjecture when it is further required to make the maximum resulting color as small as possible. In some sense, we aim at producing a number of colors that is as close as possible to the chromatic number of the graph. We first investigate the hardness of determining the minimum maximum color by a labeling for a given graph, which we show is NP -complete in the class of bipartite graphs but polynomial-time solvable in the class of graphs with bounded treewidth. We then provide bounds on the minimum maximum color that can be generated both in the general context, and for particular classes of graphs. Finally, we study how using larger labels permit to reduce the maximum color. [ABSTRACT FROM AUTHOR]

Let G be a (not necessarily properly) edge-colored graph. A compatible spanning circuit in G is a closed trail containing all vertices of G in which any two consecutively traversed edges have distinct colors. As two extremal cases, the existence of compatible (i.e., properly edge-colored) Hamilton cycles and compatible Euler tours have been studied extensively. More recently, sufficient conditions for the existence of compatible spanning circuits visiting each vertex v of G at least ⌊ (d (v) − 1) ∕ 2 ⌋ times in graphs satisfying Ore-type degree conditions have been established. In this paper, we continue the research on sufficient conditions for the existence of compatible spanning circuits visiting each vertex at least a specified number of times. We respectively consider graphs satisfying Fan-type degree conditions, graphs with a high edge-connectivity, and the asymptotical existence of such compatible spanning circuits in random graphs. [ABSTRACT FROM AUTHOR]