Abstract: The 2-domination number γ2(G) of a graph G is the minimum cardinality of a set D ⊆ V (G) for which every vertex outside D is adjacent to at least two vertices in D. Clearly, γ2(G) cannot be smaller than the domination number γ(G). We consider a large class of graphs and characterize those members which satisfy γ2 = γ. For the general case, we prove that it is NP-hard to decide whether γ2 = γ holds. We also give a necessary and sufficient condition for a graph to satisfy the equality hereditarily. PubDate: Tue, 22 Mar 2022 00:00:00 GMT
Abstract: Edge degree conditions have been studied since the 1980s, mostly with regard to hamiltonicity of line graphs and the equivalent existence of dominating closed trails in their root graphs, as well as the stronger property of being supereulerian, i.e., admitting a spanning closed trail. For a graph G, let σ¯2(G)=min{ d(u)+d(v) uv∈E(G) }{\bar \sigma _2}\left( G \right) = \min \left\{ {d\left( u \right) + d\left( v \right) uv \in E\left( G \right)} \right\}. Chen et al. conjectured that a 3-edge-connected graph G with sufficientl large order n and σ¯2(G)>n9-2{\bar \sigma _2}\left( G \right) > {n \over 9} - 2 is either supereulerian or contractible to the Petersen graph. We show that the conjecture is true when σ¯2(G)≥2(⌊ n/15 ⌋−1){\bar \sigma _2}\left( G \right) \ge 2\left( {\left\lfloor {n/15} \right\rfloor - 1} \right). Furthermore, we show that for an essentially k-edge-connected graph G with sufficiently large order n, the following statements hold.(i) If k = 2 and σ¯2(G)≥2(⌊ n/8 ⌋−1){\bar \sigma _2}\left( G \right) \ge 2\left( {\left\lfloor {n/8} \right\rfloor - 1} \right), then either L(G) is hamiltonian or G can be contracted to one of a set of six graphs which are not supereulerian;(ii) If k = 3 and σ¯2(G)≥2(⌊ n/15 ⌋−1){\bar \sigma _2}\left( G \right) \ge 2\left( {\left\lfloor {n/15} \right\rfloor - 1} \right), then either L(G) is hamiltonian or G can be contracted to the Petersen graph. PubDate: Tue, 22 Mar 2022 00:00:00 GMT
Abstract: Let G be a graph and C a finite set of colours. A vertex colouring f : V (G) → C is complete if for any pair of distinct colours c1, c2 ∈ C one can find an edge {v1, v2} ∈ E(G) such that f(vi) = ci, i = 1, 2. The achromatic number of G is defined to be the maximum number achr(G) of colours in a proper complete vertex colouring of G. In the paper achr(K6 □ Kq) is determined for any integer q such that either 8 ≤ q ≤ 40 or q ≥ 42 is even. PubDate: Tue, 22 Mar 2022 00:00:00 GMT
Abstract: As natural relaxations of pancyclic graphs, we say a graph G is kpancyclic if G contains cycles of each length from k to V (G) and G is weakly pancyclic if it contains cycles of all lengths from the girth to the circumference of G, while G is weakly k-pancyclic if it contains cycles of all lengths from k to the circumference of G. A cycle C is chorded if there is an edge between two vertices of the cycle that is not an edge of the cycle. Combining these ideas, a graph is chorded pancyclic if it contains chorded cycles of each length from 4 to the circumference of the graph, while G is chorded k-pancyclic if there is a chorded cycle of each length from k to V (G) . Further, G is chorded weakly k-pancyclic if there is a chorded cycle of each length from k to the circumference of the graph. We consider conditions for graphs to be chorded weakly k-pancyclic and chorded k-pancyclic. PubDate: Fri, 18 Feb 2022 00:00:00 GMT
Abstract: For an integer s ≥ 0, G is s-hamiltonian-connected if for any vertex subset S ⊆ V (G) with S ≤ s, G − S is hamiltonian-connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see [Reflections on graph theory, J. Graph Theory 10 (1986) 309–324]), and Kužel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian-connected (see [Z. Ryjáček and P. Vrána, Line graphs of multigraphs and Hamilton-connectedness of claw-free graphs, J. Graph Theory 66 (2011) 152–173]). In this paper we prove the following. (i) For s ≥ 3, every (s + 4)-connected line graph is s-hamiltonian-connected. (ii) For s ≥ 0, every (s + 4)-connected line graph of a claw-free graph is s-hamiltonian-connected. PubDate: Fri, 18 Feb 2022 00:00:00 GMT
Abstract: We consider the class of 2-connected cubic graphs having only k-cycles in each 2-factor, and obtain the following two results: (i) every 2-connected cubic graph having only 8-cycles in each 2-factor is isomorphic to a unique Hamiltonian graph of order 8; and (ii) a 2-connected cubic planar graph G has only k-cycles in each 2-factor if and only if k = 4 and G is the complete graph of order 4. PubDate: Fri, 18 Feb 2022 00:00:00 GMT
Abstract: In 1940, Lebesgue proved that every 3-polytope contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences:(6, 6, 7, 7, 7), (6, 6, 6, 7, 9), (6, 6, 6, 6, 11), (5, 6, 7, 7, 8), (5, 6, 6, 7, 12), (5, 6, 6, 8, 10), (5, 6, 6, 6, 17), (5, 5, 7, 7, 13), (5, 5, 7, 8, 10), (5, 5, 6, 7, 27), (5, 5, 6, 6, ∞), (5, 5, 6, 8, 15), (5, 5, 6, 9, 11), (5, 5, 5, 7, 41), (5, 5, 5, 8, 23), (5, 5, 5, 9, 17), (5, 5, 5, 10, 14), (5, 5, 5, 11, 13). In this paper we prove that every 3-polytope without vertices of degree from 7 to 11 contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences: (5, 5, 6, 6, ∞), (5, 6, 6, 6, 15), (6, 6, 6, 6, 6), where all parameters are tight. PubDate: Tue, 19 Jun 2018 00:00:00 GMT
Abstract: A graph is said to be equitably k-colorable if the vertex set V (G) can be partitioned into k independent subsets V1, V2, . . . , Vk such that Vi − Vj ≤ 1 (1 ≤ i, j ≤ k). A graph G is equitably k-choosable if, for any given k-uniform list assignment L, G is L-colorable and each color appears on at most ⌈ V(G) k⌉$\left\lceil {{{\left {V(G)} \right } \over k}} \right\rceil$ vertices. In this paper, we prove that if G is a graph such that mad(G) < 3, then G is equitably k-colorable and equitably k- choosable where k ≥ max{Δ(G), 4}. Moreover, if G is a graph such that 125${{12} \over 5}$, then G is equitably k-colorable and equitably k-choosable where k ≥ max{Δ (G), 3}. PubDate: Tue, 19 Jun 2018 00:00:00 GMT
Abstract: We only consider finite tournaments. The dual of a tournament is obtained by reversing all the arcs. A tournament is selfdual if it is isomorphic to its dual. Given a tournament T, a subset X of V (T) is a module of T if each vertex outside X dominates all the elements of X or is dominated by all the elements of X. A tournament T is decomposable if it admits a module X such that 1 < X < V (T) .We characterize the decomposable tournaments whose subtournaments obtained by removing one or two vertices are selfdual. We deduce the following result. Let T be a non decomposable tournament. If the subtournaments of T obtained by removing two or three vertices are selfdual, then the subtournaments of T obtained by removing a single vertex are not decomposable. Lastly, we provide two applications to tournaments reconstruction. PubDate: Tue, 19 Jun 2018 00:00:00 GMT
Abstract: Let T1, T2, . . . , Tk be spanning trees of a graph G. For any two vertices u, v of G, if the paths from u to v in these k trees are pairwise openly disjoint, then we say that T1, T2, . . . , Tk are completely independent. Araki showed that the square of a 2-connected graph G on n vertices with n ≥ 4 has two completely independent spanning trees. In this paper, we prove that the k-th power of a k-connected graph G on n vertices with n ≥ 2k has k completely independent spanning trees. In fact, we prove a stronger result: if G is a connected graph on n vertices with δ(G) ≥ k and n ≥ 2k, then the k-th power Gk of G has k completely independent spanning trees. PubDate: Tue, 19 Jun 2018 00:00:00 GMT
Abstract: We consider γ-graphs, which are reconfiguration graphs of the minimum dominating sets of a graph G. We answer three open questions about γ- graphs of trees by providing upper bounds on the maximum degree, the diameter, and the number of minimum dominating sets. The latter gives an upper bound on the order of the γ-graph. PubDate: Tue, 19 Jun 2018 00:00:00 GMT
Abstract: The paper deals with Hamiltonian and pancyclic graphs in the class of all self-centered graphs of radius 2. For both of the two considered classes of graphs we have done the following. For a given number n of vertices, we have found an upper bound of the minimum size of such graphs. For n ≤ 12 we have found the exact values of the minimum size. On the other hand, the exact value of the maximum size has been found for every n. Moreover, we have shown that such a graph (of order n and) of size m exists for every m between the minimum and the maximum size. For n ≤ 10 we have found all nonisomorphic graphs of the minimum size, and for n = 11 only for Hamiltonian graphs. PubDate: Tue, 19 Jun 2018 00:00:00 GMT
Abstract: A sequence is called non-repetitive if none of its subsequences forms a repetition (a sequence r1r2⋯r2n such that ri = rn+i for all 1 ≤ i ≤ n). Let G be a graph whose vertices are coloured. A colouring ϕ of the graph G is non-repetitive if the sequence of colours on every path in G is non-repetitive. The Thue chromatic number, denoted by π(G), is the minimum number of colours of a non-repetitive colouring of G.In this short note we present two general upper bounds for the Thue chromatic number for the lexicographic product G ◦ H of graphs G and H with respect to some properties of the factors. One upper bound is then used to derive the exact values for π(G ◦ H) when G is a complete multipartite graph and H an arbitrary graph. PubDate: Tue, 19 Jun 2018 00:00:00 GMT
Open Access journal
[370 journals]
