You’ve been given a graph (you should have received your personal graph via email at the

beginning of week 2, and everyone in the class has a different graph), and you are asked to write   as complete a biography of your personal graph as you can.  (If you haven’t received your personal graph, please let me know as soon as possible and we’ll get that sorted.)

By a biography, I mean determining (with appropriate arguments) for your personal graph the

values of the numerical invariants and graph properties that we will work through over the course of the semester and that we will work through for our standard Examples and our class example   graph.

The bulk of your biography won’t be the table of values of these numerical invariants and graph  properties themselves, because that’s not very interesting; rather, the bulk of your biography will

be the explanation of why those numerical invariants and graph properties have those particular values for your personal graph. That is, calculating the values of the numerical invariants and

graph properties for your personal graph is of far lesser importance than determining and describing and presenting coherently the reasons why.

You will also need to choose a numerical invariant that is not covered in the Notes and explore

that numerical invariant, as we have explored the numerical invariants through the Notes and the lectures through the semester. I will on occasion make note of potential numerical invariants that you may wish to consider, and you are very welcome to come up with your own, either from your own imagination or from your exploration of the literature.

USE OF TOOLS.  MATH3033 Graph Theory is not a coding module, nor it is an exercise in

using mathematical packages such as MAPLE. While it is the case that we are able to harness the power of the machine world to calculate the values of many of the numerical invariants and graph properties for your personal graph, that is not the point of this module. What for us is of far

greater importance is then to give the arguments of why these are the values so obtained, and this

should be the focus of your biography because this is what allows you to demonstrate your engagement with the material.

One of the things I’ve made available is a MAPLE worksheet that uses some of the functions in

the MAPLE GraphTheory library; you can access MAPLE via software.soton.ac.uk But my

expectation is that you use MAPLE only for checking that your argument is on the right track. If you insist upon generating code for various things, then that coding must be in addition to and

complementary to the arguments given, and you should also include a discussion of how you  developed your code and why you’re confident that your coding is producing accurate values.

It is not necessary for you to use MAPLE or to generate code. There are only a few places, such   as determining the number of 5-cycles in a graph, where I feel that there is a reasonable argument for making use of MAPLE.

There are also other tools that require care.  I want you to use your own words, rather than repeat back to me my words from the biographies of the class example graphs over the past few years. I  want to read the story you will have to tell about your own graph.  (I don’t particularly want to read versions of the story I’ve already told.) As part of that, I would ask that you not use any of

the fancy new generative artificial intelligence text generating tools. After all, if I want to know what ChatGPT knows about Graph Theory, I can ask it myself.

As a model, I will be producing a biography of our class example graph and our class example   numerical invariant and periodically posting drafts on the Blackboard site. I will make both my LaTex file, that you can use as a template for your biography if you so wish, and the PDF from that file available (via Blackboard) periodically through the semester.

OUTLINE MARKING SCHEME.  The outline marking scheme for this project is given

below. I’m not setting a word limit on your biography; that said, you can use the biographies I’ll be preparing of our class example graph and our class example numerical invariant as guides to

the approximate length you should be aiming for. Please note that between your personal graph   and our class example graph, some numerical invariants and graph properties may be more or less difficult to determine and so may require more or less discussion to establish.

− − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − −−

YOUR PERSONAL GRAPH (70 marks), to include:

· (60 marks) mathematical accuracy and coverage of the topic (including discussion, even if brief,  of each of the numerical invariants and graph properties listed below, as well as variants of these); see NUMERICAL INVARIANTS TO COVER below for some more detail on this;

· (10 marks) clarity of exposition and quality of presentation, including issues of grammar and spelling;

− − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − −−

YOUR PERSONAL NUMERICAL INVARIANT (20 marks), to include:

· its monotonicity and other basic properties, such as its connection to the numerical invariants we’ve covered through the semester;

· the exploration of its values for our standard examples (the complete and complete bipartite

graphs, the Kneser graphs and the co-prime graphs, paths and cycles); and

· the exploration of its value for your personal graph.

− − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − −−

YOUR PERSONAL REFLECTION (10 marks)

The inclusion of a reflective section in which you discuss the work you did over the semester in

producing the biography of your personal graph and the biography of your personal numerical

invariant. This might include discussion of the numerical invariants and graph properties that you felt were easy to determine for your personal graph and those you felt were more difficult or very  difficult, as well as the easy and difficult aspects of your analysis of your personal numerical

invariant.

− − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − − −−

NUMERICAL INVARIANTS TO COVER.  There are a number of numerical invariants

and graph properties that I expect you to determine (or at least make a solid effort to determine) for your personal graph. These include

· order, size and connectedness;

· degrees of vertices and the numerical invariants and graph properties associated to degree; · eccentricities of vertices and the numerical invariants and graph properties associated to

eccentricity;

· girth, Σ3 ( ·) and σ3 ( ·);

· circumference and Hamiltonian-ness;

· Eulerian-ness and the length of a shortest closed walk containing edge at least once;

· clique number, independence number, edge independence number and total independence number;

· the automorphism group aut( ·) and transitivity;

· chromatic number, chromatic index and total chromatic number;

· domination number and total domination number, edge domination number and total edge domination number, independent domination number;

· connectivity and edge connectivity; and

· planarity.

As a note, it may not be possible to determine the exact value of these invariants for your personal graph and that is absolutely fine, but you should include a discussion of what

exploration you’ve undertaken for each of them. Overall, this collection of numerical invariants and graph properties make up 50 marks out of the 60 marks mentioned above.

There are also other numerical invariants that arise from the numerical invariants we cover, that you are welcome to explore for your personal graph. For example (and this is a non-exhaustive   list), there are

· the complete domination number and the total complete domination number;

· secondary numerical invariants, such as the number of sets of vertices containing α( ·) or γ( ·) vertices

· edge variants for some of the numerical invariants given above, such as those arising from degree and eccentricity;

· the number of different Hamiltonian cycles, should your personal graph be Hamiltonian.

I have reserved 10 marks from the 60 marks mentioned above for this additional exploration beyond the list given just above.

WAY STATION POINTS.  I have set three way station points during the semester, at which you can submit particular pieces of your biography, on which I will provide formative feedback

and constructive commentary. I am doing this in part to help you structure your time over the course of the semester, so that you are not needing to pull everything together at the end of the  semester. These are Friday 28 October, 18 November, and 9 December. At each of these, I will ask for some specific aspect of your work, and I will provide feedback, normally within one week.

SUBMISSION.  The due date is Thursday 11 January 2024 at 16.00 (UK local time). You will submit your assignment electronically (details to follow, but using the same system as used for the Waystation Points), so please be sure to allow yourself sufficient time to make sure that it is uploaded in good time. There is a standard University late penalty, the details of which can be  found at the bottom of