The Experts below are selected from a list of 10383 Experts worldwide ranked by ideXlab platform
Marietjie Frick - One of the best experts on this subject based on the ideXlab platform.
-
Nested Locally Hamiltonian Graphs and the Oberly-Sumner Conjecture
2018Co-Authors: Johan P. De Wet, Marietjie FrickAbstract:A graph G is locally P, abbreviated LP, if for every vertex v in G the Open Neighbourhood N (v) of v is non-empty and induces a graph with property P. Specifically, a graph G without isolated vertices is locally connected (LC) if N (v) induces a connected graph for each v ∈ V (G), and locally hamiltonian (LH) if N (v) induces a hamiltonian graph for each v ∈ V (G). A graph G is locally locally P (abbreviated L 2 P) if N (v) is non-empty and induces a locally P graph for every v ∈ V (G). This concept is generalized to an arbitrary degree of nesting, to make it possible to work with L k C and L k H graphs for any integer k ≥ 0 (with L 0 C and L 0 H meaning connected and hamiltonian, respectively.) We call a graph locally k-nested hamiltonian if it is L m C for m = 0, 1,. .. k and L k H. The class of locally k-nested-hamiltonian graphs contains important subclasses. For example, Skupien had already observed in 1963 that the class of connected LH graphs (which is the class of locally 1-nested-hamiltonian graphs) contains all triangulations of closed surfaces. We show that for any k ≥ 1 the class of locally k-nested-hamiltonian graphs contains all simple-clique (k + 2)-trees. In 1979 Oberly and Sumner proved that every connected K1,3-free graph that is locally connected is hamiltonian.They conjectured that for every k ≥ 1, every connected K 1,k+3-free graph that is locally (k + 1)-connected is hamiltonian. We show that locally k-nested-hamiltonian graphs are locally (k + 1)-connected and consider the weaker conjecture that every K 1,k+3-free graph that is locally k-nested-hamiltonian is hamiltonian. We show that if our conjecture is true, it would be "best possible" in the sense that for every k ≥ 1 there exist K 1,k+4-free locally k-nested-hamiltonian graphs that are nonhamiltonian. We also attempt to establish the minimum order of nonhamiltonian locally k-nested-hamiltonian graphs and investigate the complexity of the Hamilton Cycle Problem for locally k-nested-hamiltonian graphs with restricted maximum degree.
-
Hamiltonicity of locally hamiltonian and locally traceable graphs
Discrete Applied Mathematics, 2018Co-Authors: Johan P. De Wet, Marietjie Frick, Susan A. Van AardtAbstract:Abstract If P is a given graph property, we say that a graph G is locally P if 〈 N ( v ) 〉 has property P for every v ∈ V ( G ) where 〈 N ( v ) 〉 is the induced graph on the Open Neighbourhood of the vertex v . We consider the complexity of the Hamilton Cycle Problem for locally traceable and locally hamiltonian graphs with small maximum degree. The problem is fully solved for locally traceable graphs with maximum degree 5 and also for locally hamiltonian graphs with maximum degree 6 (van Aardt et al., 2016). We show that the Hamilton Cycle Problem is NP-complete for locally traceable graphs with maximum degree 6 and for locally hamiltonian graphs with maximum degree 10. We also show that there exist regular connected nonhamiltonian locally hamiltonian graphs with connectivity 3, thus answering two questions posed by Pareek and Skupien (1983).
-
On Saito’s Conjecture and the Oberly–Sumner Conjectures
Graphs and Combinatorics, 2017Co-Authors: Susan A. Aardt, Marietjie Frick, Jean E. Dunbar, Ortrud R. OellermannAbstract:For a given graph property $$\mathcal {P}$$ P , we say a graph G is locally $$\mathcal {P}$$ P if for each $$v \in V(G)$$ v ∈ V ( G ) , the subgraph induced by the Open Neighbourhood of v has property $$\mathcal P$$ P . A closed locally $$\mathcal {P}$$ P graph is defined analogously in terms of closed Neighbourhoods. It is known that connected locally hamiltonian graphs are not necessarily hamiltonian. Saito (in Computational Geometry and Graph Theory, Lecture Notes in Computer Science, vol. 4535, pp. 191–200. Springer, Berlin, 2008 ) conjectured that if G is a graph of order at least 3 such that for every vertex v in G the subgraph induced by the closed Neighbourhood N [ v ] of v satisfies the Chvátal–Erdős condition for hamiltonicity, then G is hamiltonian. Oberly and Sumner (in J Graph Theory 3:351–356, 1979 ) conjectured that if G is a connected, locally k -connected $$K_{1,k+2}$$ K 1 , k + 2 -free graph of order at at least 3, then G is hamiltonian. We prove a result that lends support to both these conjectures. We also provide a framework for investigating these and other related conjectures.
-
Global cycle properties in locally connected, locally traceable and locally hamiltonian graphs
Discrete Applied Mathematics, 2016Co-Authors: Susan A. Van Aardt, Ortrud R. Oellermann, Marietjie Frick, Johan P. De WetAbstract:Let P be a graph property. A graph G is said to be locally P if the subgraph induced by the Open Neighbourhood of every vertex in G has property P . Ryjacek's well-known conjecture that every connected, locally connected graph is weakly pancyclic motivated us to consider the global cycle structure of locally P graphs, where P is, in turn, 'connected', 'traceable' and 'hamiltonian'. We show that (i) the locally connected graphs with maximum degree at most 5 are all weakly pancyclic, but infinitely many are nonhamiltonian, (ii) all the connected, locally traceable graphs with maximum degree at most 5 are fully cycle extendable, except for three exceptional graphs, (iii) all the connected, locally hamiltonian graphs with maximum degree at most 6 are fully cycle extendable, (iv) if G is a locally hamiltonian graph G of order n and maximum degree at least n - 5 , then G is weakly pancyclic.
Ortrud R. Oellermann - One of the best experts on this subject based on the ideXlab platform.
-
On Saito’s Conjecture and the Oberly–Sumner Conjectures
Graphs and Combinatorics, 2017Co-Authors: Susan A. Aardt, Marietjie Frick, Jean E. Dunbar, Ortrud R. OellermannAbstract:For a given graph property $$\mathcal {P}$$ P , we say a graph G is locally $$\mathcal {P}$$ P if for each $$v \in V(G)$$ v ∈ V ( G ) , the subgraph induced by the Open Neighbourhood of v has property $$\mathcal P$$ P . A closed locally $$\mathcal {P}$$ P graph is defined analogously in terms of closed Neighbourhoods. It is known that connected locally hamiltonian graphs are not necessarily hamiltonian. Saito (in Computational Geometry and Graph Theory, Lecture Notes in Computer Science, vol. 4535, pp. 191–200. Springer, Berlin, 2008 ) conjectured that if G is a graph of order at least 3 such that for every vertex v in G the subgraph induced by the closed Neighbourhood N [ v ] of v satisfies the Chvátal–Erdős condition for hamiltonicity, then G is hamiltonian. Oberly and Sumner (in J Graph Theory 3:351–356, 1979 ) conjectured that if G is a connected, locally k -connected $$K_{1,k+2}$$ K 1 , k + 2 -free graph of order at at least 3, then G is hamiltonian. We prove a result that lends support to both these conjectures. We also provide a framework for investigating these and other related conjectures.
-
Global cycle properties in locally connected, locally traceable and locally hamiltonian graphs
Discrete Applied Mathematics, 2016Co-Authors: Susan A. Van Aardt, Ortrud R. Oellermann, Marietjie Frick, Johan P. De WetAbstract:Let P be a graph property. A graph G is said to be locally P if the subgraph induced by the Open Neighbourhood of every vertex in G has property P . Ryjacek's well-known conjecture that every connected, locally connected graph is weakly pancyclic motivated us to consider the global cycle structure of locally P graphs, where P is, in turn, 'connected', 'traceable' and 'hamiltonian'. We show that (i) the locally connected graphs with maximum degree at most 5 are all weakly pancyclic, but infinitely many are nonhamiltonian, (ii) all the connected, locally traceable graphs with maximum degree at most 5 are fully cycle extendable, except for three exceptional graphs, (iii) all the connected, locally hamiltonian graphs with maximum degree at most 6 are fully cycle extendable, (iv) if G is a locally hamiltonian graph G of order n and maximum degree at least n - 5 , then G is weakly pancyclic.
-
Global properties of graphs with local degree conditions
arXiv: Combinatorics, 2015Co-Authors: Ewa Kubicka, Grzegorz Kubicki, Ortrud R. OellermannAbstract:Let P be a graph property. A graph G is said to be locally P (closed locally P, respectively) if the subgraph induced by the Open Neighbourhood (closed Neighbourhood, respectively) of every vertex in G has property P. A graph G of order n is said to satisfy Dirac’s condition if �(G) ≥ n/2 and it satisfies Ore’s condition if for every pair u,v of non-adjacent vertices in G, deg(u) + deg(v) ≥ n. A graph is locally Dirac (locally Ore, respectively) if the subgraph induced by the Open Neighbourhood of every vertex satisfies Dirac’s condition (Ore’s condition, respectively). In this paper we establish global properties for graphs that are locally Dirac and locally Ore. In particular we show that these graphs, of sufficiently large order, are 3-connected. For locally Dirac graphs it is shown that the edge connectivity equals the minimum degree and it is illustrated that this results does not extend to locally Ore graphs. We show that ⌊n/3⌋ − 1 is a sharp upper bound on the diameter of every locally Dirac graph of order n. We show that there exist infinite families of planar closed locally Dirac graphs. In contrast, locally Dirac graphs of sufficiently large order are shown to be non-planar. It is known that every closed locally Ore graph is hamiltonian. We show that locally Dirac graphs have an even richer cycle structure by showing that
Johan P. De Wet - One of the best experts on this subject based on the ideXlab platform.
-
Nested Locally Hamiltonian Graphs and the Oberly-Sumner Conjecture
2018Co-Authors: Johan P. De Wet, Marietjie FrickAbstract:A graph G is locally P, abbreviated LP, if for every vertex v in G the Open Neighbourhood N (v) of v is non-empty and induces a graph with property P. Specifically, a graph G without isolated vertices is locally connected (LC) if N (v) induces a connected graph for each v ∈ V (G), and locally hamiltonian (LH) if N (v) induces a hamiltonian graph for each v ∈ V (G). A graph G is locally locally P (abbreviated L 2 P) if N (v) is non-empty and induces a locally P graph for every v ∈ V (G). This concept is generalized to an arbitrary degree of nesting, to make it possible to work with L k C and L k H graphs for any integer k ≥ 0 (with L 0 C and L 0 H meaning connected and hamiltonian, respectively.) We call a graph locally k-nested hamiltonian if it is L m C for m = 0, 1,. .. k and L k H. The class of locally k-nested-hamiltonian graphs contains important subclasses. For example, Skupien had already observed in 1963 that the class of connected LH graphs (which is the class of locally 1-nested-hamiltonian graphs) contains all triangulations of closed surfaces. We show that for any k ≥ 1 the class of locally k-nested-hamiltonian graphs contains all simple-clique (k + 2)-trees. In 1979 Oberly and Sumner proved that every connected K1,3-free graph that is locally connected is hamiltonian.They conjectured that for every k ≥ 1, every connected K 1,k+3-free graph that is locally (k + 1)-connected is hamiltonian. We show that locally k-nested-hamiltonian graphs are locally (k + 1)-connected and consider the weaker conjecture that every K 1,k+3-free graph that is locally k-nested-hamiltonian is hamiltonian. We show that if our conjecture is true, it would be "best possible" in the sense that for every k ≥ 1 there exist K 1,k+4-free locally k-nested-hamiltonian graphs that are nonhamiltonian. We also attempt to establish the minimum order of nonhamiltonian locally k-nested-hamiltonian graphs and investigate the complexity of the Hamilton Cycle Problem for locally k-nested-hamiltonian graphs with restricted maximum degree.
-
Hamiltonicity of locally hamiltonian and locally traceable graphs
Discrete Applied Mathematics, 2018Co-Authors: Johan P. De Wet, Marietjie Frick, Susan A. Van AardtAbstract:Abstract If P is a given graph property, we say that a graph G is locally P if 〈 N ( v ) 〉 has property P for every v ∈ V ( G ) where 〈 N ( v ) 〉 is the induced graph on the Open Neighbourhood of the vertex v . We consider the complexity of the Hamilton Cycle Problem for locally traceable and locally hamiltonian graphs with small maximum degree. The problem is fully solved for locally traceable graphs with maximum degree 5 and also for locally hamiltonian graphs with maximum degree 6 (van Aardt et al., 2016). We show that the Hamilton Cycle Problem is NP-complete for locally traceable graphs with maximum degree 6 and for locally hamiltonian graphs with maximum degree 10. We also show that there exist regular connected nonhamiltonian locally hamiltonian graphs with connectivity 3, thus answering two questions posed by Pareek and Skupien (1983).
-
Traceability of locally hamiltonian and locally traceable graphs
Discrete Mathematics & Theoretical Computer Science, 2016Co-Authors: Johan P. De Wet, Susan A. Van AardtAbstract:If $\mathcal{P}$ is a given graph property, we say that a graph $G$ is locally $\mathcal{P}$ if $\langle N(v) \rangle$ has property $\mathcal{P}$ for every $v \in V(G)$ where $\langle N(v) \rangle$ is the induced graph on the Open Neighbourhood of the vertex $v$. Pareek and Skupien (C. M. Pareek and Z. Skupien , On the smallest non-Hamiltonian locally Hamiltonian graph, J. Univ. Kuwait (Sci.), 10:9 - 17, 1983) posed the following two questions. Question 1 Is 9 the smallest order of a connected nontraceable locally traceable graph? Question 2 Is 14 the smallest order of a connected nontraceable locally hamiltonian graph? We answer the second question in the affirmative, but show that the correct number for the first question is 10. We develop a technique to construct connected locally hamiltonian and locally traceable graphs that are not traceable. We use this technique to construct such graphs with various prescribed properties.
-
Global cycle properties in locally connected, locally traceable and locally hamiltonian graphs
Discrete Applied Mathematics, 2016Co-Authors: Susan A. Van Aardt, Ortrud R. Oellermann, Marietjie Frick, Johan P. De WetAbstract:Let P be a graph property. A graph G is said to be locally P if the subgraph induced by the Open Neighbourhood of every vertex in G has property P . Ryjacek's well-known conjecture that every connected, locally connected graph is weakly pancyclic motivated us to consider the global cycle structure of locally P graphs, where P is, in turn, 'connected', 'traceable' and 'hamiltonian'. We show that (i) the locally connected graphs with maximum degree at most 5 are all weakly pancyclic, but infinitely many are nonhamiltonian, (ii) all the connected, locally traceable graphs with maximum degree at most 5 are fully cycle extendable, except for three exceptional graphs, (iii) all the connected, locally hamiltonian graphs with maximum degree at most 6 are fully cycle extendable, (iv) if G is a locally hamiltonian graph G of order n and maximum degree at least n - 5 , then G is weakly pancyclic.
Susan A. Van Aardt - One of the best experts on this subject based on the ideXlab platform.
-
Hamiltonicity of locally hamiltonian and locally traceable graphs
Discrete Applied Mathematics, 2018Co-Authors: Johan P. De Wet, Marietjie Frick, Susan A. Van AardtAbstract:Abstract If P is a given graph property, we say that a graph G is locally P if 〈 N ( v ) 〉 has property P for every v ∈ V ( G ) where 〈 N ( v ) 〉 is the induced graph on the Open Neighbourhood of the vertex v . We consider the complexity of the Hamilton Cycle Problem for locally traceable and locally hamiltonian graphs with small maximum degree. The problem is fully solved for locally traceable graphs with maximum degree 5 and also for locally hamiltonian graphs with maximum degree 6 (van Aardt et al., 2016). We show that the Hamilton Cycle Problem is NP-complete for locally traceable graphs with maximum degree 6 and for locally hamiltonian graphs with maximum degree 10. We also show that there exist regular connected nonhamiltonian locally hamiltonian graphs with connectivity 3, thus answering two questions posed by Pareek and Skupien (1983).
-
Traceability of locally hamiltonian and locally traceable graphs
Discrete Mathematics & Theoretical Computer Science, 2016Co-Authors: Johan P. De Wet, Susan A. Van AardtAbstract:If $\mathcal{P}$ is a given graph property, we say that a graph $G$ is locally $\mathcal{P}$ if $\langle N(v) \rangle$ has property $\mathcal{P}$ for every $v \in V(G)$ where $\langle N(v) \rangle$ is the induced graph on the Open Neighbourhood of the vertex $v$. Pareek and Skupien (C. M. Pareek and Z. Skupien , On the smallest non-Hamiltonian locally Hamiltonian graph, J. Univ. Kuwait (Sci.), 10:9 - 17, 1983) posed the following two questions. Question 1 Is 9 the smallest order of a connected nontraceable locally traceable graph? Question 2 Is 14 the smallest order of a connected nontraceable locally hamiltonian graph? We answer the second question in the affirmative, but show that the correct number for the first question is 10. We develop a technique to construct connected locally hamiltonian and locally traceable graphs that are not traceable. We use this technique to construct such graphs with various prescribed properties.
-
Global cycle properties in locally connected, locally traceable and locally hamiltonian graphs
Discrete Applied Mathematics, 2016Co-Authors: Susan A. Van Aardt, Ortrud R. Oellermann, Marietjie Frick, Johan P. De WetAbstract:Let P be a graph property. A graph G is said to be locally P if the subgraph induced by the Open Neighbourhood of every vertex in G has property P . Ryjacek's well-known conjecture that every connected, locally connected graph is weakly pancyclic motivated us to consider the global cycle structure of locally P graphs, where P is, in turn, 'connected', 'traceable' and 'hamiltonian'. We show that (i) the locally connected graphs with maximum degree at most 5 are all weakly pancyclic, but infinitely many are nonhamiltonian, (ii) all the connected, locally traceable graphs with maximum degree at most 5 are fully cycle extendable, except for three exceptional graphs, (iii) all the connected, locally hamiltonian graphs with maximum degree at most 6 are fully cycle extendable, (iv) if G is a locally hamiltonian graph G of order n and maximum degree at least n - 5 , then G is weakly pancyclic.
Saudi Arabia - One of the best experts on this subject based on the ideXlab platform.
-
Properties of Soft Semi-Open and Soft semi-closed Sets
arXiv: General Mathematics, 2014Co-Authors: Sabir Hussain, Saudi ArabiaAbstract:Molodstov[10] introduced soft set theory as a new mathematical approach for solving problems having uncertainties. Many researchers worked on the findings of structures of soft set theory and applied to many problems having uncertainties. Recently, Bin Chen [3-4] introduced and explored the properties of soft semi-Open sets and soft-semi-closed sets in soft topological spaces. In this paper we continue to investigate the properties of soft semi-Open and soft semi-closed sets in soft topological spaces. We define soft semi-exterior, soft semi-boundary, soft semi-Open Neighbourhood and soft semi-Open Neighbourhood systems in soft topological spaces. Moreover we discuss the characterizations and properties of soft semi-interior, soft semi-exterior, soft semi-closure and soft semi-boundary. We also develop the relationship between soft semi-clOpen sets and soft semi-boundary. The addition of this topic in literature will strengthen the theoretical base for further applications of soft topology in decision analysis and information systems.
