### Archives For graph theory

A couple months ago, my colleague Jeff Rushall and I co-applied for a Center for Undergraduate Research in Mathematics (CURM) mini-grant to fund a group of undergraduate students to work on an academic-year research project. Jeff and I had both individually applied in the past, but neither of us were successful in our proposals. If you are interested, you can take a look at my previous proposal by going here. Jeff and I are both passionate about undergraduate research and work well together. We decided that a joint application would likely be stronger than two individual proposals. I’m happy to report that we recently found out that our proposal was funded. We’re thrilled!

Here are a few more details. For the upcoming project, we recruited a diverse group of 7 talented undergraduates: Michael Hastings (one of my current research students), Emily White, Hanna Prawzinsky, Alyssa Whittemore, Levi Heath, Brianha Preston, and Nathan Diefenderfer. Students are expected to spend ten hours per week during the academic year working on the research project. In return, each student will earn a $\$3000$stipend. Money from the grant will also be used to buyout a single course for both me and Jeff. In addition, Jeff and I will team-teach a topics course each semester that will include our research students but will also be open to other interested students. CURM will cover most of the travel expenses for Jeff and I to attend the Faculty Summer Workshop at Brigham Young University (BYU). CURM will also cover most of the travel expenses for the nine of us to attend the Student Research Conference at BYU. A collaborative research program has many advantages over operating several disconnected projects, as Jeff and I have done in the past. One of our goals is to build a self-sustaining research group. Ideally, this group will consist of students at different stages of their education, each participating for multiple years. The opportunities afforded by a CURM mini-grant will provide a catalyst for our endeavor in several ways. First, the visibility of a student research group with a CURM mini-grant will help our department recruit mathematically inclined students. NAU has many such students, but some are enticed by existing research groups and grants in our science programs. Second, we would like to take advantage of the mentoring and training the CURM program provides for faculty. One weakness in my past projects is getting students to finish writing up their results for publication. I am hopeful that my involvement in CURM will help remedy this. Third, we believe that the stipend money will enable our students to forgo some of their part-time work and instead devote their time to mathematics. Lastly, we want to use the experience as a stepping stone towards obtaining an externally funded REU program. Next year’s research project involves “prime labelings of graphs,” which is outside my typical research interests. Jeff and I believe that we have found a project that is accessible to undergraduates yet rich enough that we won’t even come close to running out of stuff to do. I’m really looking forward to branching out and exploring something new. If you are interested, here is the project description that we submitted. ## Project Description This research project is motivated by a conjecture in graph theory, first stated in a 1999 paper by Seoud and Youssef [1], namely: All unicyclic graphs have prime labelings. This is a viable choice as a research problem for undergraduates because it is interesting yet accessible, in large part due to the minimal amount of background information required. To wit, a unicyclic graph is a simple graph containing exactly one cycle. An$n$-vertex simple graph$G$with vertex set$V(G)$is said to have a prime labeling if there exists a bijection$f: V(G) \to \{1, 2, 3, \ldots, n\}$such that the labels assigned to adjacent vertices of$G$are relatively prime. As discussed in Gallian’s “A Dynamic Survey of Graph Labeling” [2], many families of graphs have prime labelings; the “simpler” types of unicyclic graphs that are known to have prime labelings include cycles, helms, crowns, and tadpoles. The goal of our project will be to discover additional classes of unicyclic graphs with prime labelings, in hopes of bringing the aforementioned conjecture on all unicyclic graphs within reach. The families of graphs we will investigate include, but are not limited to: 1. double-tailed tadpoles, triple-tailed tadpoles, etc.; 2. irregular crowns (crowns with paths of different lengths attached to each cycle vertex); 3. unicyclic graphs with one or more trivalent trees attached to cycle vertices; 4. unicyclic graphs with one or more complete ternary trees attached to cycle vertices; and 5. unicyclic graphs with a specified number of non-cycle cubic vertices. Seoud and Youssef have established necessary and sufficient conditions for some graphs to have prime labelings, but they are somewhat limited in scope. Seoud has also published an upper bound on the chromatic numbers of prime graphs. These and other results may be beneficial to our students as their research project progresses. Ernst and Rushall have already made some progress on these specific cases. We will use these initial results as a starting point with our team of students. More precisely, the 7 students involved in this project will attend a 3-credit research seminar during both semesters of the 2014-2015 academic year. Ernst and Rushall will team-teach the seminar, but eventually the students will play an equal role in leading discussions, presenting research results, etc. Our recent experience with Seoud’s Conjecture has indicated that this problem is ripe with potential and highly appropriate as an undergraduate research project. The students can begin productive work in a single afternoon, and yet we anticipate the students producing original results worthy of publication in refereed journals by the end of the academic year. Moreover, there appear to be a virtually unlimited number of families of graphs to investigate, which will hopefully lead to a sustainable research program for undergraduates in future years. The 7 students we have recruited to work on this research project are mathematics majors in our department. In addition, they all have very good academic records, and have proven themselves to be hard-working, reliable and creative students in previous courses that we have taught, including vector calculus, linear algebra, abstract algebra, foundations, discrete mathematics and number theory. These students regularly attend our weekly departmental undergraduate seminar, so they are familiar with the rigors associated with research and are motivated to investigate deeper problems in mathematics. It should be noted that several presentation venues (departmental, university-wide, as well as regional conferences) will be exploited to allow our students an opportunity to showcase their efforts during the 2014-2015 academic year. ## References [1] M.A. Seoud and M.Z. Youssef, “On Prime Labeling of Graphs,” Congressus Numerantium, Vol. 141, 1999, pp. 203-215. [2] J.A. Gallian, “A Dynamic Survey of Graph Labeling,” The Electronic Journal of Combinatorics, Vol. 18, 2011. http://www.combinatorics.org/Surveys/ds6.pdf This semester I am teaching a course for freshman mathematics majors. The course is called Introduction to Formal Mathematics. One purpose of the course is to develop a tight-knit cohort of mathematics majors and another purpose is show them that mathematics is about more than “solve for$x\$.” We do some problem solving, a little proof writing, and introduce them to a few topics they may or may not see in future courses.  The course is a lot of fun. Feel free to check out the course webpage.

The last couple weeks we have been doing a little combinatorics and some graph theory. Today one of the students remarked something to the effect, “I liked math before, but this stuff is just so cool.”  I agree.  There is no reason why we couldn’t teach these topics to high school students or even middle school students.  Unfortunately, we are too obsessed with trying to make sure students pass standardized tests and can take calculus in high school.