• Skip to main content
  • Skip to after header navigation
  • Skip to site footer
ERN: Emerging Researchers National Conference in STEM

ERN: Emerging Researchers National Conference in STEM

  • About
    • About AAAS
    • About the NSF
    • About the Conference
    • Partners/Supporters
    • Project Team
  • Conference
  • Abstracts
    • Undergraduate Abstract Locator
    • Graduate Abstract Locator
    • Abstract Submission Process
    • Presentation Schedules
    • Abstract Submission Guidelines
    • Presentation Guidelines
  • Travel Awards
  • Resources
    • Award Winners
    • Code of Conduct-AAAS Meetings
    • Code of Conduct-ERN Conference
    • Conference Agenda
    • Conference Materials
    • Conference Program Books
    • ERN Photo Galleries
    • Events | Opportunities
    • Exhibitor Info
    • HBCU-UP/CREST PI/PD Meeting
    • In the News
    • NSF Harassment Policy
    • Plenary Session Videos
    • Professional Development
    • Science Careers Handbook
    • Additional Resources
    • Archives
  • Engage
    • Webinars
    • ERN 10-Year Anniversary Videos
    • Plenary Session Videos
  • Contact Us
  • Login

Competition and (1,2)-Step Competition Numbers in 4-Cycle Graph Variations

Undergraduate #66
Discipline: Mathematics and Statistics
Subcategory: Mathematics and Statistics

Carissa Babcock - Alverno College


In 2013, Factor, Merz and Sano asked the question: Are there graphs other than C4, the cycle on 4 vertices, where the competition number of a graph G, k(G), is greater than its (1,2)-step competition number, k(1,2)(G)? This research is important since it is providing a partial answer to this previous research. It was thought that by looking at variations of C4 graphs, a similar pattern will be seen. The competition number of a graph G, k(G), is defined as the smallest nonnegative integer k such that a graph G with k isolated vertices is the competition graph for some acyclic digraph. Similarly, the (1,2)-step competition number is defined as the smallest nonnegative integer k such that a graph G with k isolated vertices is the (1,2)-step competition graph for some acyclic digraph. An (i,j)-step competition graph is the generalized concept in which {x,y} will be an edge in the (i,m)-step competition graph, denoted C(i,m)(D), if for some z ∈V(T)-{x,y},d_(T-y) (x,z) ≤i and d_(T-x) (y,z)≤m or d_(T-x) (y,z)≤i and d_(T-y) (x,z)≤m. The competition graph will be the (1,1)-step competition graph, and the (1,2)-step is the (1,2)-step competition graph of the generalized (i,j)-step definition. Here we explore classes of graphs that provide a partial answer to the question asked in that paper and prove that the relationship exists for C4 ∪ C4 graphs. In the future, different variations will be looked at. One concept that will be observed is C4 graphs with pendants. This research was funded by the National Science Foundation and was conducted at Marquette University in the Computation Across the Disciplines REU. Main References: [1] Dutton, R., Brigham, R. A Characterization of Competition Graphs. Discrete Applied Mathematics 6 (1983) 315-317. [2] Factor, K., Merz, S., Sano, Y. The (1,2)-step competition number of a graph. Congressus Numerantium 215, (2013) 153-161. [3] Factor, K., Merz, S. The (1,2)-step competition graph of a tournament. Discrete Applies Mathematics. Volume 159, Issues 2-3 (2011) 100-103.

Funder Acknowledgement(s): National Science Foundation

Faculty Advisor: Kim Factor, kim.factor@marquette.edu

Role: I did all of the research discussed in the abstract. I conducted research based off of questions my mentor asked when she did prior research. My results extend off of her and her research partners' results.

Sidebar

Abstract Locators

  • Undergraduate Abstract Locator
  • Graduate Abstract Locator

This material is based upon work supported by the National Science Foundation (NSF) under Grant No. DUE-1930047. Any opinions, findings, interpretations, conclusions or recommendations expressed in this material are those of its authors and do not represent the views of the AAAS Board of Directors, the Council of AAAS, AAAS’ membership or the National Science Foundation.

AAAS

1200 New York Ave, NW
Washington,DC 20005
202-326-6400
Contact Us
About Us

  • LinkedIn
  • Facebook
  • Instagram
  • Twitter
  • YouTube

The World’s Largest General Scientific Society

Useful Links

  • Membership
  • Careers at AAAS
  • Privacy Policy
  • Terms of Use

Focus Areas

  • Science Education
  • Science Diplomacy
  • Public Engagement
  • Careers in STEM

Focus Areas

  • Shaping Science Policy
  • Advocacy for Evidence
  • R&D Budget Analysis
  • Human Rights, Ethics & Law

© 2023 American Association for the Advancement of Science