The direct sum of a finite number of graph classes H_1, ..., H_k is defined as the set of all graphs formed by taking the union of graphs from each of the H_i. The join of these graph classes is similarly defined as the set of all graphs formed by taking the join of graphs from each of the H_i. In this paper we show that if each H_i has a forbidden subgraph characterization then the direct sum and join of these H_i also have forbidden subgraph characterizations. We provide various results which in many cases allow us to exactly determine the minimal forbidden subgraphs for such characterizations. As we develop these results we are led to study the minimal graphs which are universal over a given list of graphs, or those which contain each graph in the list as an induced subgraph. As a direct application of our results we give an alternate proof of a theorem of Barrett and Loewy concerning a forbidden subgraph characterization problem.
","abstract_html":"<p>The <em>direct sum</em> of a finite number of graph classes H_1, ..., H_k is defined as the set of all graphs formed by taking the union of graphs from each of the H_i. The <em>join</em> of these graph classes is similarly defined as the set of all graphs formed by taking the join of graphs from each of the H_i. In this paper we show that if each H_i has a forbidden subgraph characterization then the direct sum and join of these H_i also have forbidden subgraph characterizations. We provide various results which in many cases allow us to exactly determine the minimal forbidden subgraphs for such characterizations. As we develop these results we are led to study the minimal graphs which are <em>universal</em> over a given list of graphs, or those which contain each graph in the list as an induced subgraph. As a direct application of our results we give an alternate proof of a theorem of Barrett and Loewy concerning a forbidden subgraph characterization problem.</p>","abstract_has_math":false,"creators":["Barrus, Michael D."],"institution":"Brigham Young University - Provo","degree_name":"MS","degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-07-24T01:27:16Z","subjects":["forbidden","subgraph","graph theory","universal","Mathematics"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://scholarsarchive.byu.edu/etd/125","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Barrus, Michael D."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2004-03-17T08:00:00Z"]},{"key":"dc:publisher","label":"Institution","values":["Brigham Young University - Provo"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["forbidden","subgraph","graph theory","universal","Mathematics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://scholarsarchive.byu.edu/etd/125","https://scholarsarchive.byu.edu/context/etd/article/1124/viewcontent/ETD_CISOPTR_93.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Physical and Mathematical Sciences; Mathematics"]},{"key":"dc:description.abstract","label":"Abstract","values":["The direct sum of a finite number of graph classes H_1, ..., H_k is defined as the set of all graphs formed by taking the union of graphs from each of the H_i. The join of these graph classes is similarly defined as the set of all graphs formed by taking the join of graphs from each of the H_i. In this paper we show that if each H_i has a forbidden subgraph characterization then the direct sum and join of these H_i also have forbidden subgraph characterizations. We provide various results which in many cases allow us to exactly determine the minimal forbidden subgraphs for such characterizations. As we develop these results we are led to study the minimal graphs which are universal over a given list of graphs, or those which contain each graph in the list as an induced subgraph. As a direct application of our results we give an alternate proof of a theorem of Barrett and Loewy concerning a forbidden subgraph characterization problem.
"]},{"key":"dc:format","label":"Dc Format","values":["application:pdf"]},{"key":"dc:source","label":"Dc Source","values":["Brigham Young University - Provo"]},{"key":"dc:title","label":"Title","values":["A Forbidden Subgraph Characterization Problem and a Minimal-Element Subset of Universal Graph Classes"]}]}],"canonical_facts":{"dc:creator":["Barrus, Michael D."],"dc:date":["2004-03-17T08:00:00Z"],"dc:description":["Physical and Mathematical Sciences; Mathematics"],"dc:description.abstract":["The direct sum of a finite number of graph classes H_1, ..., H_k is defined as the set of all graphs formed by taking the union of graphs from each of the H_i. The join of these graph classes is similarly defined as the set of all graphs formed by taking the join of graphs from each of the H_i. In this paper we show that if each H_i has a forbidden subgraph characterization then the direct sum and join of these H_i also have forbidden subgraph characterizations. We provide various results which in many cases allow us to exactly determine the minimal forbidden subgraphs for such characterizations. As we develop these results we are led to study the minimal graphs which are universal over a given list of graphs, or those which contain each graph in the list as an induced subgraph. As a direct application of our results we give an alternate proof of a theorem of Barrett and Loewy concerning a forbidden subgraph characterization problem.
"],"dc:format":["application:pdf"],"dc:identifier":["https://scholarsarchive.byu.edu/etd/125","https://scholarsarchive.byu.edu/context/etd/article/1124/viewcontent/ETD_CISOPTR_93.pdf"],"dc:language":["English"],"dc:publisher":["Brigham Young University - Provo"],"dc:source":["Brigham Young University - Provo"],"dc:subject":["forbidden","subgraph","graph theory","universal","Mathematics"],"dc:title":["A Forbidden Subgraph Characterization Problem and a Minimal-Element Subset of Universal Graph Classes"],"dc:type":["Thesis"],"thesis:degree_name":["MS"]},"updated_at":"2026-07-24T01:27:16Z"}