Search

Henning et al. (Discrete Appl Math 162:399–403, 2014) proved that if G is a bipartite, cubic graph of order n and of girth at least 6, then i (G) ≤ 4 11 n . In this paper, we improve the 4 11 -bound to a 5 14 -bound, and prove that if G is a bipartite, cubic graph of order n and of girth at least 6, then i (G) ≤ 5 14 n . [ABSTRACT FROM AUTHOR]

For a graph G, define σ 2 (G) by σ 2 (G) = min { d G (x) + d G (y) : x , y ∈ V (G) , x ≠ y , x y ∉ E (G) } . If G is a bipartite graph with partite sets X and Y, we also define σ 1 , 1 (G) by σ 1 , 1 (G) = min { d G (x) + d G (y) : x ∈ X , y ∈ Y , x y ∉ E (G) } . Ore's theorem states that a graph of order n ≥ 3 with σ 2 (G) ≥ n contains a hamiltonian cycle and the Moon–Moser theorem states that a balanced bipartite graph G of order 2 n ≥ 4 with σ 1 , 1 (G) ≥ n + 1 contains a hamiltonian cycle. In Chen et al. (Discrete Math 343:Article No. 111663, 2020), we studied the relationship between Ore's theorem and the Moon–Moser theorem, and proved that the refinement of the Moon–Moser theorem given by Ferrara et al. (Discrete Math 312:459–461, 2012) implies Ore's theorem for graphs of even order. In this paper, we extend the above study to the graphs of odd order. Since no graphs of odd order contain a spanning balanced bipartite subgraph, the Moon–Moser theorem does not work in this case. We instead introduce its counterpart for the graphs in which the orders of the partite sets differ by 1, proved in Matsubara et al. (Discrete Math 340:87–95, 2017). We refine this result and prove that this refinement implies Ore's theorem. [ABSTRACT FROM AUTHOR]

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. The independent domination number of G, denoted by i(G), is the minimum cardinality of an independent dominating set. In this paper, we study the following conjecture posed by Goddard and Henning (Discrete Math. 313:839–854, 2013): If G ≇ K 3 , 3 is a connected, cubic, bipartite graph on n vertices, then i (G) ≤ 4 11 n . Henning et al. (Discrete Appl. Math. 162:399–403, 2014) prove the conjecture when the girth is at least 6. In this paper we strengthen this result by proving the conjecture when the graph has no subgraph isomorphic to K 2 , 3 . [ABSTRACT FROM AUTHOR]

A total weighting of a graph G is a mapping $$\varphi $$ that assigns a weight to each vertex and each edge of G. The vertex-sum of $$v \in V(G)$$ with respect to $$\varphi $$ is $$S_{\varphi }(v)=\sum _{e\in E(v)}\varphi (e)+\varphi (v)$$ . A total weighting is proper if adjacent vertices have distinct vertex-sums. A graph $$G=(V,E)$$ is called $$(k,k{^{\prime }})$$ -choosable if the following is true: For any total list assignment L which assigns to each vertex v a set L( v) of k real numbers, and assigns to each edge e a set L( e) of $$k{^{\prime }}$$ real numbers, there is a proper total weighting $$\varphi $$ with $$\varphi (y)\in L(y)$$ for any $$y \in V \cup E$$ . In this paper, we prove that for any graph $$G\ne K_1$$ , for any positive integer m, the m-cone graph of G is (1, 4)-choosable. Moreover, we give some sufficient conditions for the m-cone graph of G to be (1, 3)-choosable. In particular, if G is a tree, a complete bipartite graph or a generalized $$\theta $$ -graph, then the m-cone graph of G is (1, 3)-choosable. [ABSTRACT FROM AUTHOR]