Date of Graduation

2016

Document Type

Dissertation

Degree Type

PhD

College

Eberly College of Arts and Sciences

Department

Mathematics

Committee Chair

Hong-Jain Lai

Committee Co-Chair

John Goldwasser

Committee Member

Rong Luo

Committee Member

K Subramani

Committee Member

Jerzy Wojciechowski

Abstract

A digraph D is eulerian if D is connected and for any v ∈ V ( D), d+D( v) = d-D( v). A digraph D is supereulerian if D contains a spanning eulerian subdigraph. A digraph D is a closed ditrail if it is eulerian. This dissertation focuses on the sufficient conditions for a digraph to be supereulerian and we discussed it for the following conditions.;1. Matching number condition. Let D be a digraph and G be a graph. Let lambda(D) be the arc-strong connectivity of D, alpha(D) be the independence number of D, alpha'(D) be the size of a maximum matching of D, and kappa'(G) be the edge conectivity of G. Motivated by the following conjecture: Let D be a digraph. If lambda(D) ≥ alpha( D), then D is supereulerian, which has been verified in several families of digraphs. There have been investigations on supereulerian properties of a graph G with given inequality constraints on kappa'(G), alpha(G) and alpha'( G), as seen in [1], [15], [18], [22] and [23], among others. In [5], Bang-Jensen and Maddaloni also proved that if kappa'(G) ≥ alpha( G) for a graph G, then G is supereulerian. We prove that if lambda(D) ≥ alpha'(D) > 0, then D has a spanning eulerian subdigraph.;2. Locally density condition. It is well known (for example, Corollary 1 of [10]) that every connected, locally-connected graph other than K2 is supereulerian. The problem investigated in this chapter is whether strong and locally strong digraphs will behave similarly, and how local structure in digraph will warrant the existence of a spanning eulerian subdigraph. We shall prove that for any integer k > 0, there exists an infinite family of strong, k +-locally-arc-connected non-supereulerian digraphs which is also an infinite family of strong, k-locally-arc-connected non-supereulerian digraphs. These suggest that local connectivity may not be sufficient for supereulerian digraphs. This motivates us to seek whether locally dense conditions for supereulerian digraphs. Let alpha, beta be two rational numbers. A strong digraph D is locally (alpha, beta)+-arc-connected if ∀v ∈ V(D), lambda( D[N +(v)]) ≥ alpha| N+(v)| + beta. A locally (0, k)+-arc-connected digraph is also called k+-locally-arc-connected. We prove that every locally (2/3, 0)+-arc-connected strong digraph is supereulerian.;3. Forbidden induced short dipaths condition. We investigate forbidden induced subdigraph conditions to assure the existence of supereulerian digraphs. For an integer k ≥ 2, let Pk denote the dipath on k vertices. A subdigraph H of a digraph D is a Pk-subdigraph if H = Pk. If D does not have an induced Pk, then for any Pk-subdigraph H of D, we must have |A( D[V (H)])| ≥ k. For integers h ≥ k > 2, we define F(Pk, h) to be the family of all simple digraphs such that D ∈ F(P k, h) if and only if D is strong and satisfies both of the following. (i) D contains at least one dipath Pk with |A(D[ V(Pk )])| = h, and (ii) for any dipath Pk in D, | A(D[V(Pk )])| ≥ h. We determine the smallest integer h k such that if a strong digraph D containing a subdigraph H isomorphic to Pk always satisfies |A(D[V(H)])| ≥ hk with k ∈ {lcub}2, 3, 4{rcub}, then D is supereulerian.;4. Degree condition. The property of being supereulerian is at the same time a relaxation of being hamiltonian: being supereulerian means having a closed ditrail covering all the vertices; being hamiltonian means having a closed ditrail covering all the vertices without using a vertex twice (hamiltonian cycle). Motivated by this analogy with hamiltonian cycles, we obtain a sufficient degree condition for supereulerianity similar to that for hamiltonicity in [24] due to Zhao and Meng. We prove that let D be a strong digraph. If d+(x) + d+(y) + d -(u) + d-( v) ≥ 2n - 3 for every pair x, y of dominating non-adjacent vertices and every pair u, v of dominated non-adjacent vertices, then D is supereulerian.;5. Matching number and minimum degree condition for a graph. Let G be a graph. Let delta(G) be the minimum degree of G, kappa'(G) be the edge-connectivity of G, alpha(G) be the independence number of G and alpha'(G) be the size of a maximum matching of G. Motivated by the investigations on supereulerian properties of a graph G with given inequality constraints on kappa'(G), alpha(G) and alpha'( G), as seen in [1], [15], [18], [22] and [23], among others. In [5], Bang-Jensen and Maddaloni proved that if kappa'(G) ≥ alpha( G) for a graph G, then G is supereulerian. We prove that if delta(G) ≥ alpha'(G) ≥ 2, where |V(G)| is even when alpha'( G) = 2, then G has a spanning eulerian subdigraph.

Download

Share

COinS