• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • No language data
  • Tagged with
  • 5
  • 5
  • 5
  • 5
  • 5
  • 4
  • 4
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

A Characterization of <sup>P 5</sup>-Free, Diameter-2-Critical Graphs

Haynes, Teresa W., Henning, Michael A. 31 May 2014 (has links)
A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no induced path on five vertices. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n2/4 and that the extremal graphs are the complete bipartite graphs with partite sets whose cardinality differs by at most one. We use an association with total domination to prove that if G is a diameter-2-critical graph with no induced path P5, then G is triangle-free. As a consequence, we observe that the Murty-Simon Conjecture is true for P5-free, diameter-2-critical graphs by Turán's Theorem. Finally we characterize these graphs by characterizing their complements.
2

A Maximum Degree Theorem for Diameter-2-Critical Graphs

Haynes, Teresa W., Henning, Michael A., van der Merwe, Lucas C., Yeo, Anders 01 January 2014 (has links)
A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ⌊n 2/4⌋ and that the extremal graphs are the complete bipartite graphs K ⌊n/2⌋,⌊n/2⌉. Fan [Discrete Math. 67 (1987), 235-240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81-98] proved the conjecture for n > n 0 where n 0 is a tower of 2's of height about 1014. The conjecture has yet to be proven for other values of n. Let Δ denote the maximum degree of G. We prove the following maximum degree theorems for diameter-2-critical graphs. If Δ ≥ 0.7 n, then the Murty-Simon Conjecture is true. If n ≥ 2000 and Δ ≥ 0.6789 n, then the Murty-Simon Conjecture is true.
3

A Characterization of Diameter-2-Critical Graphs Whose Complements Are Diamond-Free

Haynes, Teresa W., Henning, Michael A. 01 September 2012 (has links)
A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. The complete graph on four vertices minus one edge is called a diamond, and a diamond-free graph has no induced diamond subgraph. In this paper we use an association with total domination to characterize the diameter-2-critical graphs whose complements are diamond-free. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph G of order n is at most ⌊ n24⌋ and that the extremal graphs are the complete bipartite graphs K⌊ n2⌋n2⌉. As a consequence of our characterization, we prove the Murty-Simon conjecture for graphs whose complements are diamond-free.
4

A Characterization of Diameter-2-Critical Graphs With No Antihole of Length Four

Haynes, Teresa W., Henning, Michael A. 01 June 2012 (has links)
A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no antihole of length four, that is, the diameter-2-critical graphs whose complements have no induced 4-cycle. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n 2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. As a consequence of our characterization, we prove the Murty-Simon Conjecture for graphs with no antihole of length four.
5

Realizability of the Total Domination Criticality Index

Haynes, T. W., Mynhardt, C. M., Van Der Merwe, L. C. 01 May 2005 (has links)
For a graph G = (V, E), a set S ⊆ V is a total dominating set if every vertex in V is adjacent to some vertex in S. The smallest cardinality of any total dominating set is the total domination number γt(G). For an arbitrary edge e εE(Ḡ), γt(G) - 2 ≤ γt(G + e) ≤ γt(G); if the latter inequality is strict for each e ε E(Ḡ) ≠ φ, then G is said to be γt-critical. The criticality index of an edge e ε E(Ḡ) is γt(e) = γt(G) - γt(G + e). Let E(Ḡ) = [e1...,em} and S = ∑j=1m̄ci(ej). The criticality index of G is ci(G) = S/m̄. For any rational number k, 0 ≤ k ≤ 2, we construct a graph G with ci(G) = k. For 1 ≤ k ≤ 2, we construct graphs with this property that are γt-critical as well as graphs that are not γt-critical.

Page generated in 0.1368 seconds