Copyright for this paper by its authors. Use permitted under Creative Commons
License Attribution 4.0 International (CC BY 4.0).

Proceedings of the Workshop on Empowering Education with LLMs—the Next-Gen
Interface and Content Generation held at AIED 2023, July 7, 2023, Tokyo,
Japan.

<EMAIL_ADDRESS>] [1] [1]

<EMAIL_ADDRESS>] [1] [1]

<EMAIL_ADDRESS>]

[orcid=0000-0002-9421-8566<EMAIL_ADDRESS>]

[orcid=0000-0002-3674-5456<EMAIL_ADDRESS>]

<EMAIL_ADDRESS>]

[1]Corresponding author. [1]These authors contributed equally.

# Harnessing LLMs in Curricular Design: Using GPT-4 to Support Authoring of
Learning Objectives

Pragnya Sridhar  Language Technology Institute, Carnegie Mellon University,
Pittsburgh, PA, USA  Aidan Doyle  Arav Agarwal  Computer Science Department,
Carnegie Mellon University, Pittsburgh, PA, USA  Christopher Bogart  Jaromir
Savelka  Majd Sakr

(2023)

###### Abstract

We evaluated the capability of a generative pre-trained transformer (GPT-4) to
automatically generate high-quality learning objectives (LOs) in the context
of a practically oriented university course on Artificial Intelligence.
Discussions of opportunities (e.g., content generation, explanation) and risks
(e.g., cheating) of this emerging technology in education have intensified,
but to date there has not been a study of the models’ capabilities in
supporting the course design and authoring of LOs. LOs articulate the
knowledge and skills learners are intended to acquire by engaging with a
course. To be effective, LOs must focus on what students are intended to
achieve, focus on specific cognitive processes, and be measurable. Thus,
authoring high-quality LOs is a challenging and time consuming (i.e.,
expensive) effort. We evaluated 127 LOs that were automatically generated
based on a carefully crafted prompt (detailed guidelines on high-quality LOs
authoring) submitted to GPT-4 for conceptual modules and projects of an AI
Practitioner course. We analyzed the generated LOs if they follow certain best
practices such as beginning with action verbs from Bloom’s taxonomy in regards
to the level of sophistication intended. Our analysis showed that the
generated LOs are sensible, properly expressed (e.g., starting with an action
verb), and that they largely operate at the appropriate level of Bloom’s
taxonomy, respecting the different nature of the conceptual modules (lower
levels) and projects (higher levels). Our results can be leveraged by
instructors and curricular designers wishing to take advantage of the state-
of-the-art generative models to support their curricular and course design
efforts.

###### keywords:

GPT-4 Large Language Models LLMs Learning Objectives Automatic Generation
Curricular Development Course Design Automation Automated Content Generation

##  1 Introduction

Learning objectives (LOs) are the blueprints against which course content is
designed. They provide instructors with a framework for content curation,
instructional and assessment strategies, as well as enable learners to reflect
on and plan their own learning of a course’s knowledge and skills. Alignment
between LOs, instructional strategies and assessments is a necessary
prerequisite for internally consistent learning experience. When the three
components are misaligned, learners may feel that tests do not assess what was
covered in class, or instructors may notice that students earn a passing grade
without mastering the material at the desired level. Hence, poor quality or
missing LOs have a negative impact on the learning experience.111Eberly
Center: Design & Teach a Course. Available at:
https://www.cmu.edu/teaching/designteach/design/learningobjectives.html
[Accessed 2023-05-10]

Creating effective LOs can be challenging and time-consuming for instructors,
requiring substantial knowledge and experience in instructional design. Bloom
[1, 2, 3] proposed a taxonomy organizing LOs into six levels (remember,
understand, apply, analyze, evaluate, and create). This taxonomy helps
educators articulate LOs that focus on concrete actions and behaviors, and
target distinct levels of cognitive processes. For LOs to guide the selection
of assessments, they must be measurable, i.e., it should be possible to
evaluate whether learners attained the intended objective. Because of the
complexity involved in authoring high-quality LOs, instructors often forego
the task in lieu of more pressing duties such as authoring the course content
or teaching.

Furthermore, instructors may have general notions of the learning objectives
they want students to accomplish by the course’s end. However, these notions
may not meet the criteria of being well-defined and measurable learning
objectives that focus on what a learner will achieve. To address this issue,
our aim is to develop an approach that generates high-quality learning
objectives and streamlines the objective-setting process. In our initial
experiment, we investigate the potential of utilizing Language Models (LLMs)
to generate effective learning objectives. This exploration serves as a
stepping stone for future solutions that involve refining and augmenting the
learning objectives initially provided by instructors.

Large Language Models (LLMs) are sophisticated AI models pre-trained on
extensive textual data, that can generate human-level quality text. With
appropriate prompting, an LLM might create high-quality LOs, alleviating the
burden on the instructors. In this study we explore the potential of a state-
of-the-art LLM (GPT-4) to support this task. We hypothesize that a well-
prompted LLM can more efficiently produce candidate LOs, saving instructors’
time.

To investigate the capability of GPT-4 to efficiently generate quality LOs in
the context of a software development course on the practical integration of
AI into applications, we analyzed the following research questions:

  1. RQ1:

Are the generated LOs sensible, i.e., clear grammatically correct statements,
addressing the relevant topic?

  2. RQ2:

Do the LOs start with an appropriate action verb describing measurable
behavior?

  3. RQ3:

Do the conceptual module and project-related LOs target cognitive processes at
the appropriate levels of Bloom’s taxonomy?

To our best knowledge, this is the first study that proposes and evaluates
automatic generation of LOs to drive the course design process, as opposed to
generating LOs from an already existing course materials [4].

##  2 Related Work

Several works posit that LLMs could be an asset in pedagogy in several ways
including Assessment Generation, Personalized Feedback System, generating
lesson plans and asking questions about the best ways to teach a subject [5,
6, 7]. While much work has already been done towards the applications of LLMs
and course-content generation, LLMs have yet to be shown to generate course-
guiding LOs. Thus, our focus on generating course-guiding LOs by leveraging
the abilities of LLMs.

Tran et al. used IBM Watson to automatically generate LOs based on key-phrases
extracted from course material documents paired with action verbs from Bloom’s
Taxonomy [4]. In this work, we generate LOs using state-of-the-art LLM
(GPT-4). While the system proposed in [4] employs a similar definition of LOs
to ours, the intended use is different. We generate LOs prior to course
materials to potentially guide the content generation process. The system from
[4] assumes an existing collection of course material, and generate LOs from
the collection.

Other work that harnesses LLMs to generate course material includes Multiple-
Choice Question (MCQ) generation, such as the Question-Answer-Distractor
pipeline in [8]. Lu et al. utilized LLMs to effectively generate reading
quizzes, confirming the effectiveness of the system in manual evaluation by 11
instructors across 7 different universities [9].

Adams comments on the direct application of Bloom’s Taxonomy to developing LOs
[3]. By including action verbs associated with different levels of the
taxonomy, educators are encouraged to think in terms of what students should
be able to do at the end of the course. Additionally, the authors of [4]
generated the LOs by training a multi-layer perceptron (MLP) to learn which
Bloom’s Taxonomy action verb would best fit with each of the key phrases
extracted from the collection of course material documents[4]. In this work,
the evaluation heavily focuses on verifying that the generated learning
objectives begin with an action verb from an appropriate level of Bloom’s
Taxonomy.

In computing education context, LLMs have been shown to be highly effective at
generating code and explanations of the code for entry-level programmers [10].
Such explanations have even been observed to out-class student explanations of
the same code [11]. Denny et al. discovered that well-structured prompts could
yield correct solutions to many programming exercises [12]; observations later
confirmed by Savelka et al. [13, 14]. Piccolo et al. demonstrated that LLMs
can perform most entry-level programming tasks in the context of introductory
bioinformatics course [15]. However, Savelka et al. [16] and Wermelinger [17]
point to some limitations of LLMs in handling assessments from introductory
programming classes. Phung et al. introduced a system that harnessed LLMs to
provide precision feedback on syntax errors in students’ code [18]. Such
feedback explanations went far beyond describing the code line-by-line. Sarsa
et al. found such explanations were particularly valuable for student learning
[10]. MacNeil et al. demonstrated that explanations of generated code can be
offered at multiple different levels of abstraction [19, 20]. In the near
future, it is reasonable to expect LLMs to facilitate teacher-student
exchanges similar to those that only occur in a classroom, and are invaluable
to student learning [21].

##  3 Experiments

###  3.1 Model

GPT has gained significant popularity due to its remarkable advancements in
understanding and generating natural language text. It has demonstrated
superior performance across various domains, including code generation [22],
software engineering [23], solving AI tasks [24], and data augmentation [25],
showcasing its domain-invariant capabilities. In the context of education, a
study conducted by Malinka et al. [7] specifically investigated the impact of
ChatGPT, a variant of the GPT model, on higher education with a focus on
computer programming subjects. The authors provided evidence highlighting the
effectiveness of ChatGPT in managing programming assignments, exams, and
homework tasks.

Building on the success of its predecessors, GPT-4 represents a significant
leap forward in language modeling technology [26]. Thus in our pursuit of
generating course syllabus, we use the GPT-4 model (gpt-4). As of the writing
of this paper, GPT-4 is by far the most advanced model released by OpenAI. The
model is focused on dialog between a user and a system (i.e., an assistant).

We set the `temperature` of the model to 0.7, which is the default. The higher
the `temperature` the more creative the output but it can also be less
factual. As the temperature approaches 0.0, the model becomes deterministic
and can be repetitive. We set `max_tokens` to 2,000 tokens (a token roughly
corresponds to a word). This parameter controls the maximum length of the
completion (i.e., the output). Note that GPT-4 has an overall token length
limit of 8,192 tokens, comprising both the prompt and the completion.222There
is also a variant of the model that supports up to 32,768 tokens. We set
`top_p` to 1 (default). This parameter is related to `temperature` and also
influences creativeness of the output. We set `frequency_penalty` to 0, which
allows repetition by ensuring no penalty is applied to repetitions. Finally,
we set `presence_penalty` to 0, ensuring no penalty is applied to tokens
appearing multiple times in the output.

###  3.2 Experimental Design

You are a curricular development expert system focused on authoring LOs.
Learning objectives are brief, clear statements that describe the desired
learning outcomes of instruction. [601 characters ...] LOs should use action
verbs. LOs should be measurable. A well-constructed learning objective
contains three parts [392 characters ...] 1\. BEHAVIOR The behavior is the
real work to be accomplished by the student specified by an action verb that
connotes observable and measurable behaviors. [2,497 characters ...] 2\.
CONDITIONS This is a statement that describes the exact conditions under which
the defined behavior is to be performed. [117 characters ...] 3\. DEGREE This
is a statement that specifies how well the student must perform the behavior
[171 characters ...] Conceptual LOs are focused on students’ knowledge and
understanding (i.e., the first two levels of Bloom’s taxonomy). [18 example
LOs (1,540 characters) ...] Project LOs are focused on students’ skills and
behaviors (i.e., the higher levels of Bloom’s taxonomy). [12 example LOs
(1,261 characters) ...] Here are some criteria to satisfy in order to create
an effective learning objective: 1\. LOs should be student-centered. [114
characters ...] 2\. LOs should focus on specific cognitive processes. [530
characters ...] 3\. LOs should use action verbs. 4\. LOs should be measurable
[105 characters ...] The user will provide you with the name of the course,
brief description of the course goals, the name of the module, and the type of
the LOs to be developed. Based on these you respond with a list of well-
designed effective LOs (5-10 items).

Figure 2: The system prompt. The figure shows the essential elements of the
system prompt guiding the model towards generating high-quality LOs. The grey
annotations are used as replacement for extensive parts of the prompt that
could not be fit into the figure.

To generate LOs, we utilize the system prompt illustrated in Figure 2. The
system prompt guides the GPT-4 model towards the desired behavior. The prompt
contains brief guidelines on how LOs should be structured and what properties
are desirable. These guidelines were informed by various university materials
on course design.333Eberly Center: Design & Teach a Course. Available at:
https://www.cmu.edu/teaching/designteach/design/learningobjectives.html
[Accessed 2023-05-10]; Center for Excellence in Teaching and Learning at
UCONN: Developing LOs. Available at: https://cetl.uconn.edu/resources/design-
your-course/developing-learning-objectives/ [Accessed 2023-05-10] The
guidelines instruct the system to generate LOs for conceptual modules as well
as projects. The LOs should start with an action verb describing the behavior,
state the conditions under which it is to be performed, and the degree of
mastery the learners should attend. The prompt also provides many example LOs.
These can be related to conceptual modules that focus on the two lower levels
of Bloom’s taxonomy, e.g.:

> Define DevOps from organizational, cultural and technical perspectives.

The LOs from projects focus on behaviors described by action verbs from higher
levels of Bloom’s taxonomy, e.g.:

> Design and implement Continuous Integration and Continuous Delivery for a
> Node.JS application.

The prompt emphasizes the difference between the conceptual module and project
related LOs. Hence, given the same topic the LOs for the conceptual module are
expected to differ substantially from those generated for the project in terms
of their focus on different levels of Bloom’s taxonomy.

COURSE NAME: AI Practitioner COURSE GOALS: In this course, learners gain
hands-on experience solving real-world problems by completing projects focused
on developing AI/ML-enabled systems. It is our goal that students will develop
the skills needed to become sophisticated developers of AI/ML-based systems.
Specifically, students are exposed to real-world data and scenarios to learn
how to: \- Integrated different types of AI/ML systems into their
applications, recognize their capabilities and limitations. \- Explain the
effects of data quality, quantity, and representativeness on the performance
of AI/ML systems. \- Inspect, validate, and critically assess outputs of AI/ML
systems. \- Use AI/ML components via cloud APIs or locally run libraries from
different areas, such as language technologies, or computer vision, including
state-of-the art generative models. \- Discuss the advantages and
disadvantages of different computing devices and environments for deployment
of Artificial Intelligence systems. Through this process, we aspire for our
students to become sophisticated, independent, and resilient problem solvers
who are able to overcome challenges and learn. MODULE NAME: {{module}} LOs
TYPE: {{module_type}} EXPECTED OUTPUT: 1\. Text of LO1. 2\. Text of LO2. ...

Figure 3: The User Message. The figure shows the user message template
specifying the context for the LOs to be generated. The grey orange tokens are
replaced with module specific information.

The context of the particular course being designed, i.e., AI Practitioner, is
provided to GPT-4 via the user message. The full template of the user message
used in this work is shown in Figure 3. It provides the name of the course,
brief description of the high-level course goals, placeholders for a module
name (e.g., “Generative Models” or “AI/ML in the Cloud”) and module type
(i.e., either a “conceptual module” or a “project”). To generate LOs for each
conceptual module and each project, a separate message is used with the
placeholders filled in accordingly. The dynamically constructed prompts, i.e.,
the system prompt and the user message, are submitted individually to OpenAI’s
GPT-4 API using the `openai` Python library.444GitHub: OpenAI Python Library.
Available at: https://github.com/openai/openai-python [Accessed 2023-05-10]

We extracted the generated LOs from the GPT-4 responses and analyzed them to
answer the three research questions. To answer RQ2, we used a simple regular
expression to extract the action verb from each learning objective. To answer
RQ3, we evaluated the generated LOs using both automatic methods and human
annotation. We presented the 127 of the LOs to 3 graduate computer science
students and asked them to classify them into the individual levels of Bloom’s
Taxonomy. Out of these, 101 LOs were annotated by all three of the annotators.
We also automatically classified the generated LOs into the individual levels
of Bloom’s taxonomy using the approach mentioned in [27]. They trained a
binary classifier for each Bloom’s Taxonomy category using a dataset of 21,380
LOs from 5,558 university courses. We used the same models to predict the
Bloom’s Taxonomy level of the generated LOs.

###  3.3 Results

Figure 4 shows that LOs for conceptual modules heavily employ a small number
of action verbs such as “describe,” “discuss,” “explain,” “identify” and
“define”. This is expected since these verbs are geared toward conceptual
learning. The LOs for projects use more diverse set of action verbs. The
examples include “implement,” “optimize,” “develop,” or “utilize.” These verbs
also appear sensible as they focus on activities and skills as opposed to
conceptual knowledge.

Figure 4: Distribution of action verbs across module types.

Figure 5 reports the distribution of LOs across the conceptual modules and
projects categorized in terms of Bloom’s Taxonomy categories, using the
classifier proposed in [27]. The LOs generated for conceptual modules
predominantly fall under the “Understand” level, while the LOs generated for
projects are spread across the “Apply,” “Analyze,” “Evaluate,” and “Create”
levels. This is expected. Figure 6 shows similar distribution where instead of
the BERT-based classifier we use levels of Bloom’s taxonomy assigned by each
of our human annotators. Note that the counts in this figure are normalized,
as each LO was annotated three times during human annotation. The distribution
differs a bit but we can still observe the LOs for the conceptual modules
mostly employing the action verbs from the lower levels of Bloom’s taxonomy,
whereas the LOs for projects use action verbs from the higher levels.

Figure 5: Bloom’s Taxonomy Categorization of Generated LOs using BERT Figure
6: Bloom’s Taxonomy Categorization of Generated LOs based on Human Annotation

##  4 Discussion

###  4.1 RQ1: Are the generated LOs sensible?

Overall, the LOs are largely sensible. They describe key sub-concepts related
to the relevant topic, and mostly focus on one or two separate cognitive
processes, e.g.:

> Explain the key concepts and techniques used in computer vision, such as
> image processing, feature extraction, and object recognition.

GPT-4 generates LOs with action verbs such as “describe,” “explain,” and
“discuss” for conceptual modules, and “implement,” “evaluate” and “develop”
for project-based materials. While the LOs are sensible they sometimes lack
specific focus. For example, one such generated LO was “Implement a basic
AI/ML model using Python libraries to solve a simple classification or
regression problem.” While this is measurable, the term “Python libraries” is
too broad, and would benefit from being more focused (e.g., “scikit-learn”).
This issue may be solvable with further prompt tuning.

###  4.2 RQ2: Do the LOs start with an appropriate action verb?

All the LOs start with action verbs. The distribution of action verbs across
LOs for conceptual modules and projects is as expected. Action verbs such as
“describe” and “explain” should be associated with conceptual materials often
focused on declarative knowledge. Whereas action verbs such as “implement” and
“develop” should be associated with projects geared towards procedural
knowledge.

We found that some generated LOs (Figure 4) employed action verbs that were
not included in the extensive list of example verbs provided to the model via
the prompt. Specifically, these were “optimize,” “preprocess,” “explore,”
“document,” “implement,” “utilize,” and “process”. Of these, only “utilize”
and “implement” appeared in the examples mentioned in the prompt. Of the 127,
there were 26 LOs starting with action verbs not included in the list of
examples: 25 of these were for projects and one was for a conceptual module.
Moreover, there were 13 LOs with action verbs that have that were not provided
anywhere in the prompt.

Furthermore, there are 11 generated LOs that utilize multiple action verbs,
e.g., “Evaluate the performance of computer vision models using appropriate
metrics and develop strategies to improve their accuracy and reliability.”
These could have been separate LOs (e.g., “Evaluate the performance of
computer vision models using appropriate metrics.” and “Develop strategies to
improve the accuracy and reliability of computer vision models”).

###  4.3 RQ3: Do the LOs target cognitive processes at the appropriate levels
of Bloom’s taxonomy?

The results of applying BERT classifier as described in Section 3.2 show that
the GPT-4 model generates LOs that largely operate on the expected levels of
Bloom’s Taxonomy (Figure 5). Conceptual modules are more focused on
declarative knowledge, and the LOs mostly employ action verbs from the lower
two levels of Bloom’s taxonomy (Remember and Understand). Projects are focused
on procedural knowledge, and the LOs mostly use action verbs from the higher
four levels (Apply, Analyze, Evaluate and Create). Based on the BERT
classifier, it appears that the generated LOs are geared towards the
appropriate types of cognitive processes.

The classifier proposed in [27] may have some limitations. We noticed that two
of the generated LOs were not assigned to any of the Bloom’s Taxonomy levels,
while five LOs were assigned multiple categories. Note that these issues
pertain to a relatively small proportion of the generated LOs.

We presented the generated LOs to human annotators to validate the BERT-based
classification. As seen in Figure 5, most LOs generated for conceptual modules
were classified as targeting the Understand and Remember levels of Bloom’s
taxonomy, and most project LOs were classified as _not_ Understand or
Remember. This same distribution can be observed in 6, although with a higher
frequency for humans classifying conceptual LOs as ’Remember’ instead of
’Understand’. When conducting the human annotation, we used Cohen’s $K$ to
examine our inter-rater agreement. The average agreement among raters for
classifying LOs into each of the six individual levels of Bloom’s Taxonomy was
0.31, corresponding to fair agreement. By mapping the BERT and human
classifications to the corresponding LO categories, we were able to observe an
agreement between the majority-vote annotation and the BERT classification of
0.62, demonstrating substantial agreement between the human and BERT
classification of LOs into either the ’Remember’ and ’Understand’, or the
’Apply’, ’Analyze’, ’Evaluate’, and ’Create’ levels of Bloom’s Taxonomy.

##  5 Implications for Education Practice

Automatic generation of LOs could significantly ease the workload of
educators, allowing them to focus more on teaching and student interaction.
Automation could improve the quality of LOs. Reducing the cost of authoring
LOs could open up a possibility of personalized LOs for each student based on
their individual strengths, weaknesses, and progress. On the other hand, the
over-reliance on automated systems could potentially lead to a loss of
pedagogical nuance and adaptability. The standardization might stifle
creativity and innovation in teaching methods. Therefore, integrating such
systems into teaching practice should be handled with caution, ensuring they
serve as a supportive tool rather than a replacement for educators’ expertise.

##  6 Limitations

LOs drive the entire course development process. Mistakes in authoring LOs may
cascade and snowball into larger issues manifesting in low-quality course
content. LLMs are relatively new technology, and there may be skepticism or
resistance from educators and experts regarding the reliability and validity
of using LLMs to generate LOs. Addressing these concerns and gaining
acceptance is essential for potential widespread adoption of the proposed
approach. Additionally, there is a need for human validation of the generated
LOs. While LLMs can assist in the initial generation process, human expertise
and judgment are crucial to ensure the accuracy, relevance, and
appropriateness of the generated LOs. Some instructors or institutions have
suggested use of GPT to be unethical because of its training on copyrighted
materials. Hence, its products may not be usable in institutions with policies
preventing such use.

##  7 Conclusions and Future Work

This paper explored the use of LLMs for generating LOs in the context of
practically oriented university course on AI. Prior work demonstrated the
effectiveness of LLMs in various tasks in educational context, even in
generating various elements of course content. This work highlights the
potential of LLMs for generating LOs to support curricular development. We
evaluated the effectiveness of GPT-4 on this task. We found that the generated
LOs are sensible, properly expressed (e.g., starting with an action verb), and
that they largely operate at the appropriate level of Bloom’s taxonomy
respecting the different nature of the conceptual modules (lower levels) and
projects (higher levels). These findings can be leveraged by instructors and
curricular designers wishing to take advantage of the state-of-the-art
generative models to support their curricular and course design efforts. In
future work, we plan to further evaluate the generated LOs, especially in
terms of the LOs being measurable. This may include generating LOs for
existing courses with existing human-created LOs in order to compare the two.
In addition, GPT-4 could also be used for developemn of assessment strategies
for the generated LOs.

## References

  * Bloom et al. [1956] B. S. Bloom, M. D. Engelhart, E. Furst, W. H. Hill, D. R. Krathwohl,  Handbook i: cognitive domain,  New York: David McKay (1956).
  * Krathwohl [2002] D. R. Krathwohl,  A revision of bloom’s taxonomy: An overview,  Theory into practice 41 (2002) 212–218.
  * Adams [2015] N. E. Adams,  Bloom’s taxonomy of cognitive learning objectives.,  Journal of the Medical Library Association : JMLA 103 3 (2015) 152–3.
  * Tran et al. [2018] K. N. Tran, J. H. Lau, D. Contractor, U. Gupta, B. Sengupta, C. J. Butler, M. Mohania,  Document chunking and learning objective generation for instruction design,  in: EDM, International EDM Society, 2018.
  * Su and Yang [0] J. Su, W. Yang,  Unlocking the power of chatgpt: A framework for applying generative ai in education,  ECNU Review of Education 0 (0) 20965311231168423. URL: https://doi.org/10.1177/20965311231168423. doi:10.1177/20965311231168423.
  * Kasneci et al. [2023] E. Kasneci, K. Seßler, S. Küchemann, M. Bannert, D. Dementieva, F. Fischer, U. Gasser, G. Groh, S. Günnemann, E. Hüllermeier, et al., Chatgpt for good? on opportunities and challenges of large language models for education, 2023. URL: edarxiv.org/5er8f. doi:10.35542/osf.io/5er8f.
  * Malinka et al. [2023] K. Malinka, M. Perešíni, A. Firc, O. Hujňák, F. Januš, On the educational impact of chatgpt: Is artificial intelligence ready to obtain a university degree?, 2023\. arXiv:2303.11146.
  * Rodriguez-Torrealba et al. [2022] R. Rodriguez-Torrealba, E. Garcia-Lopez, A. Garcia-Cabot,  End-to-end generation of multiple-choice questions using text-to-text transfer transformer models,  Expert Syst. Appl. 208 (2022). URL: https://doi.org/10.1016/j.eswa.2022.118258. doi:10.1016/j.eswa.2022.118258.
  * Lu et al. [2023] X. Lu, S. Fan, J. Houghton, L. Wang, X. Wang,  Readingquizmaker: A human-nlp collaborative system that supports instructors to design high-quality reading quiz questions,  Proceedings of the 2023 CHI Conference on Human Factors in Computing Systems (2023).
  * Sarsa et al. [2022] S. Sarsa, P. Denny, A. Hellas, J. Leinonen,  Automatic generation of programming exercises and code explanations using large language models,  ACM, 2022. URL: https://doi.org/10.1145%2F3501385.3543957. doi:10.1145/3501385.3543957.
  * Leinonen et al. [2023] J. Leinonen, P. Denny, S. MacNeil, S. Sarsa, S. Bernstein, J. Kim, A. Tran, A. Hellas, Comparing code explanations created by students and large language models, 2023. arXiv:2304.03938.
  * Denny et al. [2022] P. Denny, V. Kumar, N. Giacaman, Conversing with copilot: Exploring prompt engineering for solving cs1 problems using natural language, 2022. arXiv:2210.15157.
  * Savelka et al. [2023a] J. Savelka, A. Agarwal, C. Bogart, Y. Song, M. Sakr,  Can generative pre-trained transformers (gpt) pass assessments in higher education programming courses?,  arXiv preprint arXiv:2303.09325 (2023a).
  * Savelka et al. [2023b] J. Savelka, A. Agarwal, M. An, C. Bogart, M. Sakr,  Thrilled by your progress! large language models (gpt-4) no longer struggle to pass assessments in higher education programming courses,  arXiv preprint arXiv:2306.10073 (2023b).
  * Piccolo et al. [2023] S. R. Piccolo, P. Denny, A. Luxton-Reilly, S. Payne, P. G. Ridge, Many bioinformatics programming tasks can be automated with chatgpt, 2023. arXiv:2303.13528.
  * Savelka et al. [2023] J. Savelka, A. Agarwal, C. Bogart, M. Sakr, Large language models (gpt) struggle to answer multiple-choice questions about code, 2023. arXiv:2303.08033.
  * Wermelinger [2023] M. Wermelinger,  Using github copilot to solve simple programming problems (2023).
  * Phung et al. [2023] T. Phung, J. P. Cambronero, S. Gulwani, T. Kohn, R. Majumdar, A. K. Singla, G. Soares,  Generating high-precision feedback for programming syntax errors using large language models,  ArXiv abs/2302.04662 (2023).
  * MacNeil et al. [2022] S. MacNeil, A. Tran, D. Mogil, S. Bernstein, E. Ross, Z. Huang,  Generating diverse code explanations using the gpt-3 large language model,  ICER ’22, Association for Computing Machinery, New York, NY, USA, 2022. URL: https://doi.org/10.1145/3501709.3544280. doi:10.1145/3501709.3544280.
  * MacNeil et al. [2023] S. MacNeil, A. Tran, A. Hellas, J. Kim, S. Sarsa, P. Denny, S. Bernstein, J. Leinonen,  Experiences from using code explanations generated by large language models in a web software development e-book,  SIGCSE 2023, ACM, New York, NY, USA, 2023, p. 931–937. URL: https://doi.org/10.1145/3545945.3569785. doi:10.1145/3545945.3569785.
  * Tan et al. [2023] K. Tan, T. Pang, C. Fan, Towards applying powerful large ai models in classroom teaching: Opportunities, challenges and prospects, 2023. arXiv:2305.03433.
  * Wollowski [2023] M. Wollowski,  Using chatgpt to produce code for a typical college-level assignment,  AI Magazine 44 (2023) 129–130. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/aaai.12086. doi:https://doi.org/10.1002/aaai.12086. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/aaai.12086.
  * White et al. [2023] J. White, S. Hays, Q. Fu, J. Spencer-Smith, D. C. Schmidt, Chatgpt prompt patterns for improving code quality, refactoring, requirements elicitation, and software design, 2023\. arXiv:2303.07839.
  * Shen et al. [2023] Y. Shen, K. Song, X. Tan, D. Li, W. Lu, Y. Zhuang, Hugginggpt: Solving ai tasks with chatgpt and its friends in hugging face, 2023. arXiv:2303.17580.
  * Dai et al. [2023] H. Dai, Z. Liu, W. Liao, X. Huang, Y. Cao, Z. Wu, L. Zhao, S. Xu, W. Liu, N. Liu, S. Li, D. Zhu, H. Cai, L. Sun, Q. Li, D. Shen, T. Liu, X. Li, Auggpt: Leveraging chatgpt for text data augmentation, 2023. arXiv:2302.13007.
  * OpenAI [2023] OpenAI, Gpt-4 technical report, 2023\. arXiv:2303.08774.
  * Li et al. [2022] Y. Li, M. Rakovic, B. X. Poh, D. Gasevic, G. Chen,  Automatic classification of learning objectives based on bloom’s taxonomy,  in: A. Mitrovic, N. Bosch (Eds.), EDM, International EDM Society, Durham, United Kingdom, 2022, pp. 530–537. doi:10.5281/zenodo.6853191.


# Bounds on the Inducibility of Double Loop Graphs

S. Y. Chan Deakin University, Geelong, Australia, School of Information
Technology, Faculty of Science Engineering & Built Environment, Australia K.
Morgan††footnotemark:  J. Ugon11footnotemark: 1

###### Abstract

In the area of extremal graph theory, there exists a problem that investigates
the maximum induced density of a $k$-vertex graph $H$ in any $n$-vertex graph
$G$. This is known as the problem of _inducibility_ that was first introduced
by Pippenger and Golumbic in 1975. In this paper, we give a new upper bound
for the inducibility for a family of _Double Loop Graphs_ of order $k$. The
upper bound obtained for order $k=5$ is within a factor of 0.964506 of the
exact inducibility, and the upper bound obtained for $k=6$ is within a factor
of 3 of the best known lower bound.

##  1 Introduction

A problem in extremal graph theory investigates the maximum induced density of
a $k$-vertex graph $H$ in any $n$-vertex graph $G$. The asymptotic behaviour
of the limit of this maximum induced density of $H$ in different classes of
graphs have been studied. This relates to the problem of inducibility that was
first introduced by Pippenger and Golumbic [56] in 1975, which was defined as
follows:

Given a graph $H$ of order $k$, we count the maximum number of $k$-vertex
subsets in a graph G of order $n\geq k$, that induce a copy of $H$. Let
$\mathcal{P}(H,G)$ denote the number of induced copies $H$ (up to isomorphism)
in $G$, where $G$ and $H$ are simple graphs. This number lies between 0 and
$\binom{n}{k}$. Since we are only interested in the limit as
$n\rightarrow\infty$, we normalise $\mathcal{P}(H,G)$ by defining the
inducibility of $H$

$\mathcal{I}(H,G)=\dfrac{\mathcal{P}(H,G)}{\binom{n}{k}}.$ (1)

Let $\mathcal{P}(H,n)$ denote the maximum number of induced copies of $H$
taken over all graphs of order $n$. Again, we normalise this by setting

$\mathcal{I}(H,n)=\dfrac{\mathcal{P}(H,n)}{\binom{n}{k}}.$ (2)

Note that

$0\leq\mathcal{I}(H,G),\mathcal{I}(H,n)\leq 1.$ (3)

Pippenger and Golumbic showed that for any graph $H$, the sequence
$\mathcal{I}(H,n)$ is non-increasing and bounded below by 0 and approaches a
limit as $n\rightarrow\infty$. Thus, the inducibility of $H$ is defined as

$\mathcal{I}(H)=\lim_{n\rightarrow\infty}\mathcal{I}(H,n).$ (4)

The exact inducibility $\mathrm{I}(H)$ of only a handful of graphs and graph
classes is currently known. This includes some graphs of small order [3, 23,
36] and complete multipartite graphs [8, 11]. Pippenger and Golumbic gave an
initial lower bound on the inducibility for all $k$-vertex graphs,

$\mathcal{I}(H)\geq\dfrac{k!}{k^{k}-k}\geq\dfrac{(2\pi
k)^{\frac{1}{2}}}{e^{k}}.$ (5)

This lower bound was obtained using a _balanced iterated blow-up of graph
$H$_, a graph obtained by an iterative process of replacing each vertex of $G$
with copies of $H$. This lower bound that was obtained using this method of
construction was later proven to be tight for any chosen graph $H$ by Fox et
al. [26]. The authors showed, for a random graph $H$, that the maximum number
of induced copies of $H$ in $G$ is best obtained by the balanced iterated
blow-ups of $H$.

Trivially, we note that the complete graph $K_{n}$ and its complement
$\overline{K_{n}}$ have inducibility 1. The inducibility
$\mathcal{I}(H)=\mathcal{I}(\overline{H})$, thus, one need only consider one
graph from each complementary pair to obtain the inducibility. The exact
inducibilities of graphs on less than 4 vertices are known, except for the
self-complementary path on 4 vertices ($P_{4}$). Table 1 gives some results
and constructions from Exoo [24], giving the known exact inducibility of
graphs of small order and their respective extremal constructions.

Pippenger and Golumbic provided results on some families of graphs in [56].
For cycles $C_{k}$, the authors conjectured the following lower bound and
showed that this lower bound is tight for this family of graphs.

######  Conjecture 1 (Pippenger and Golumbic [56]).

For $k\geq 5$, $\mathcal{I}(C_{k})=\dfrac{k!}{k^{k}-k}$.

The condition where $k\geq 5$ is necessary, as $C_{3}=K_{3}$ and
$C_{4}=K_{2,2}$ and the inducibility of $K_{n}$ and $K_{n,n}$ are precisely
known. However, Conjecture 1 still remains unsolved [33]. Further, the authors
also showed that

$\mathcal{P}(C_{k},n)\leq\dfrac{2n}{k}\cdot(\dfrac{n-1}{k-1})^{k-1}$ (6)

such that

$\mathcal{I}(C_{k})\leq 2e\cdot\dfrac{k!}{k^{k}}.$ (7)

Equation (7) decreases the gap between the upper bound and lower bound of
$\mathcal{I}(C_{k})$ with a multiplicative factor of $2e$. This upper bound
was later improved by Hefetz and Tyomkyn (Theorem 4.0.2) in [33] for all
cycles of size $k\geq 6$. The bound by Hefetz and Tyomkyn improved the gap to
a factor of $\frac{128}{81}e$. Note that the exact inducibility for cycles of
size $k=5$ was solved by Balogh et al. [3], by using a nested blow-up of
$C_{5}$, to obtain $\mathcal{I}(C_{5})=\frac{1}{26}$.

######  Theorem 1 (Král et al. [44]).

Let $G$ be a graph of size $n$ and $C_{k}$ be a cycle of length $k\geq 6$.
Then $\mathcal{P}(C_{k},n)\leq\dfrac{2n^{k}}{k^{k}}$.

Theorem 1 improves the upper bound for $\mathcal{I}(C_{k})$ further closing
the gap between the upper and lower bounds by a multiplicative factor of 2 as
follows

$\dfrac{k!}{k^{k}-k}\leq\mathcal{I}(C_{k})\leq(2+o(1))\cdot\dfrac{k!}{k^{k}}.$
(8)

Pippenger and Golumbic also computed the inducibility of $K_{\rho,\rho}$ and
$K_{\rho,\rho+1}$. Note that for simplicity, we rewrite their original theorem
(Theorem 10 from [56]) as

######  Theorem 2 (Pippenger and Golumbic [56]).

For all $n\geq 2\rho\geq 3$: The maximum number of induced subgraphs
isomorphic to the complete bipartite graph $K_{\rho,\rho}$ in any graph of
order $n$ is

$\mathcal{P}(K_{\rho,\rho},n)=\binom{\lceil{\frac{n}{2}}\rceil}{\rho}\binom{\lfloor{\frac{n}{2}}\rfloor}{\rho},$

and the inducibility is given by

$\mathcal{P}(K_{\rho,\rho})=\dfrac{\binom{2\rho}{\rho}}{2^{2\rho}}.$

Similarly, for the complete bipartite graph $K_{\rho,\rho+1}$, where $n\geq
2\rho+1$, they have

$\mathcal{P}(K_{\rho,\rho+1},n)=\binom{\lceil{\frac{n}{2}}\rceil}{\rho}\binom{\lfloor{\frac{n}{2}}\rfloor}{\rho+1}+\binom{\lfloor{\frac{n}{2}}\rfloor}{\rho}\binom{\lceil{\frac{n}{2}}\rceil}{\rho},$

and

$\mathcal{P}(K_{\rho,\rho+1})=\dfrac{\binom{2\rho+1}{\rho}}{2^{2\rho}}.$

Pippenger and Golumbic [56] also provided a bound for some operations on
graphs. Take a graph $G$ of order $k$ and $G^{\prime}$ of order $k^{\prime}$.
Then the _conjunction_ $G\wedge G^{\prime}$ is a single graph that consists of
the disjoint graphs $G$ and $G^{\prime}$. The _disjunction_ $G\vee G^{\prime}$
is a connected graph that contains the disjoint graphs $G$ and $G^{\prime}$
but with all possible edges added between $G$ and $G^{\prime}$. The authors
gave the following bound:

######  Theorem 3 (Theorem 6 Pippenger and Golumbic [56]).

Let $G$ be a graph of order $k$ and $G^{\prime}$ a graph of order
$k^{\prime}$,

$\begin{rcases}\mathcal{I}(G\wedge G^{\prime})\\\ \mathcal{I}(G\vee
G^{\prime})\end{rcases}\geq\dfrac{(k+k^{\prime})!k^{k}k^{\prime
k^{\prime}}}{k!k^{\prime}!(k+k^{\prime})^{k+k^{\prime}}}\mathcal{I}(G)\mathcal{I}(G^{\prime})$
(9)

Some recent work [32] gives sharp asymptotic results for larger graphs for
$k\geq 5$. Razborov’s theory of flag algebra [59] has been a useful tool for
proving results of inducibility of larger graphs. The case of
$\mathcal{I}(P_{4})$ remains an open problem, however. Currently, the best
known upper bound [59] and lower bound [23] of $\mathcal{I}(P_{4})$ have been
found using flag algebra and the flagmatic software by Vaughan [72].

$H$ |  | $\bar{H}$ |  | $\mathcal{I}(H)$ | Extremal Construction
---|---|---|---|---|---
$K_{3}=C_{3}$ |  | $\overline{K_{3}}/A_{3}$ |  | 1 | A Complete Graph
$P_{3}=K_{1,2}$ |  | $\overline{P_{3}}$ |  | $\frac{3}{4}$ | A Complete Bipartite Graph
$K_{4}$ |  | $\overline{K_{4}}/A_{4}$ |  | 1 | A Complete Graph
$S_{4}$ |  | $\overline{S_{4}}$ |  | $\frac{1}{2}$ | A Complete Bipartite Graph
$C_{4}=K_{2,2}$ |  | $\overline{C_{4}}$ |  | $\frac{3}{8}$ | A Complete Bipartite Graph
$K_{paw}$ |  | $\overline{K_{paw}}$ |  | $\frac{3}{8}$ | Two Disjoint Complete Bipartite Graphs
$K_{1,1,2}$ |  | $\overline{K_{1,1,2}}$ |  | $\frac{72}{125}$ | A Complete 5-equipartite Graph
$P_{4}$ |  | $\overline{P_{4}}$ |  | $?$ | Undetermined
Table 1: The known inducibility of graphs of order 3 and 4 [23].

###  1.1 Some Bounds and Construction Methods

The inducibility of some family of graphs have been determined, i.e., complete
graph $K_{k}$ [56], complete bipartite graph $K_{\rho,\rho}$,$K_{\rho,\rho+1}$
[56] and complete multipartite graphs $K_{k,\ldots,k}$ [11]. Inducibility of
various graph classes have also been studied, such as $d$-ary trees [19],
rooted trees [20], directed paths [15], oriented stars [38], net graphs [5]
and random Cayley graphs [26]. The precise inducibility of paths of order
$k\geq 4$ or cycles of order $k\geq 6$ are still unknown [25].

In the case of $P_{4}$, Exoo’s construction [24] gave an initial lower bound
of $\frac{960}{4877}\approx 0.1968$ and an upper bound of $\frac{1}{3}$. The
bounds were attained by the of blow-up of the _Paley Graph_. The upper bound
was first improved to $\approx 0.2064$ by Hirst [36] using semi-definite
programming methods. Vaughan [72] found the currently best known upper bound
of $\approx 0.204513$ using Flag algebra method [59]. Even-Zohar and Linial
[23] improved the lower bound to $\frac{1173}{5824}\approx 0.2014$ using a
combination of the Erdös conjecture [22] and Thomason’s construction [66].
Table 2 summarises the results.

Name & Author(s) |  Lower Bound |  Upper Bound |  Construction
---|---|---|---
Pippenger & Golumbic [56], Exoo [24] |  $\mathcal{I}(P_{k})\geq\dfrac{k!}{(k+1)^{k-1}-1}$ |  $\mathcal{I}(P_{k})\leq\dfrac{k!}{2(k-1)^{k-1}}$ |  Nested blow-up of graphs.
Exoo [24] |  $\mathcal{I}(P_{4})\geq\dfrac{960}{4877}\approx 0.1968$ |  $\mathcal{I}(P_{4})\leq\dfrac{1}{3}\approx 0.3333$ |  Paley Graphs of order $p\cong 1\pmod{4}$.
Hirst [36] |  _unknown_ |  $\mathcal{I}(P_{4})\leq 0.2064$ |  Semi-definite method.
Vaughan [72] |  _unknown_ |  $\mathcal{I}(P_{4})\approx 0.204513$ |  Flag algebra calculus.
Even-Zohar [23] |  $\mathcal{I}(P_{4})\geq\dfrac{1173}{5824}\approx 0.2014$ |  _unknown_ |  Combination of Erdös conjecture [22] and Thomason’s construction [66].
Table 2: Summary of known bounds and constructions for $P_{4}$.

The exact inducibility of only some 5-vertex graphs has been determined. The
exact inducibility results for some of the 5-vertex graphs were found using
nested blow-ups [23]. The authors also adapted the Erdös-Rényi random graph as
the extremal construction for some of the 5-vertex graphs. For further
readings on the inducibility of 5-vertex graphs and the extremal construction,
the reader is referred to [23].

It is interesting to note that random graphs and probabilistic methods have
been one of the chosen tools in solving the inducibility problem for some
classes of graphs [23, 26, 74]. Currently, the best known validation tool for
extremal combinatorics is the flagmatic [72] software based on Flag algebra
[59]. However, the exact inducibility and extremal construction of some graph
classes are not yet determined, including $P_{4}$ and some of the graphs on
5-vertices.

###  1.2 Motivation

In this paper, we will investigate the inducibility of a family of _circulant_
graphs. These are special cases of _Cayley graphs_.

######  Definition 1.

Let $G$ be a finite group and $S$ be a subgroup of $G$ that contains non-
identity elements. The _Cayley_ graph $X=\mathcal{C}(G,S)$ is an undirected
graph with vertex set $V(X)=G$ and edge set $E(X)=\\{g,gh:g\in G,h\in S\\}$,
such that $S$ is symmetric and generates $G$.

Cayley graphs contain symmetrical properties and are widely studied in many
disciplines. In areas of computer science, Cayley graphs have been used in
quantum error correction and error-correcting codes in quantum systems [16,
67, 71, 75]. Further, this family of graphs have also been studied in relation
to Boolean functions [4, 57, 60]. In network topology, Cayley graphs are tools
for studying the impact on the reliability of a network, fault tolerance and
effective routing (communication) within networks, where vertices represent
processing elements and edges represent the communication lines in the network
[14, 31, 35, 37, 40, 49, 63, 65, 69, 70, 73, 76].

In biology, Cayley graphs are used in the areas of genomics, particularly in
the effects of genome arrangements based on permutation of groups and graph
convexity, since permutations are used to represent gene sequences in genomes
and chromosomes [17, 18, 21, 27, 46, 50]. In the areas of chemistry, Cayley
graphs have been used for tracking atoms as a result of a sequence of chemical
reactions, in order to anticipate the occurrence of the product molecules [34,
53]. Chemical graphs represented by Cayley graphs are also used to study the
_Wiener Index_ [43].

Cayley graphs were originally first used in explaining the concept of abstract
groups, and have been of particular interests amongst group theorists. One of
the problems in this area utilises group theory to study the spectra of this
family of graphs [2, 12, 58]. Another problem in this area investigates the
relationship between finite groups on surfaces and Cayley graphs [9, 10, 68].

Circulant graphs are a special subset of Cayley graphs. They are Cayley graphs
for the cyclic group $\mathbb{Z}_{n}$ [28]. A 3-jump circulant graph on 12
vertices is an undirected Cayley graph. Like Cayley graphs, circulant graphs
also have symmetrical properties that enable rerouting of networks, network
security and even used in peer-to-peer networking [42, 45, 47]. This family of
graphs has a nice cyclic property that contains extra connections (graph
edges).

In networks, these circulant graphs are used in terminal rerouting,
communication or broadcasting problems [13, 61, 54, 55, 62]. For example, if
there is a redundancy in a traffic network, the (extra) edges can prevent
unnecessary long routes for information to travel between terminals. Further,
the family of circulant graphs are also studied in the shortest path problems
[61, 48]. The topology and metrics of circulant graphs are also of interest
[1, 39, 51, 52, 64].

In most cases, circulant graphs have specified _jump lengths_. These jump
lengths can be constant or non-constant. One of the simplest families of
circulant graphs are cycles. A cycle of order $n$ is a 1-jump circulant graph
where $DLG(a,b)=DLG(-1,1)$. Although, cycles are one of the highly studied
families of graphs in the areas of inducibility, the exact inducibility of
cycles of order $k\geq 6$ still remains unknown. In this paper, we are
interested in 2-jump circulant graphs, or _Double loop graphs_.

######  Definition 2 (Double loop graph [6]).

Let $a,b,n$ be integers with $0<a\neq b<\frac{n}{2}$; the vertices of the
_double loop graph_ $DLG(a,b)$ are the integers modulo $n$, each vertex $i$
being joined to the four vertices $i\pm a\pmod{n}$, $i\pm b\pmod{n}$.

Figure 1: A double loop graph $DLG(1,2)$ on 6 vertices.

Double loop graphs are circulant graphs and so are of interest in the areas
discussed above. Work has been done of finding a minimum 2-terminal routing
using such graphs [61]. Other topics include cycle decomposition [7], the
shortest path problems [29], the dispersability of circulant graphs [41] and
optimal routing [30]. In this paper, we give bounds on the inducibility of
2-jump circulant graphs, $DLG(1,2)$.

##  2 Notations and Definitions

In this section, we present some basic definitions and notations that are used
in this paper. All graphs in this paper are simple.

A graph $G$ is a pair $(V,E)$, such that $V$ is the (finite) set of vertices
and $E$ is a subset of all unordered pair of vertices. The _order_ of a graph
is the number of vertices, whereas the _size_ of a graph is the number of
edges. Let $u,v\in V(G)$, we say that $u$ is _adjacent_ to $v$ if there exists
an edge $\\{u,v\\}\in E(G)$. We say that the edge $\\{u,v\\}$ is incident to
vertices $u$ and $v$.

######  Definition 3.

Let $G$ and $H$ be graphs. If there exists an edge-preserving bijective
function $\phi:E(G)\rightarrow E(H)$, such that:

$\forall(u,v)\in V(G)\times V(G),(u,v)\in
E(G)\leftrightarrow(\phi(u),\phi(v))\in E(H),$

then $G$ and $H$ are isomorphic, denoted $G\cong H$.

######  Definition 4.

Let $G$ and $G_{1}$ be graphs of order $n$ and $k$ respectively, where $n\geq
k$. We say that $G_{1}$ is a subgraph of $G$ if $V(G_{1})\subseteq V(G)$ and
$E(G_{1})\subseteq E(G)$. The graph $G_{1}$ is an induced subgraph of $G$ if
all the edges between the pairs of vertices in $V(G_{1})$ from $E$ are in
$E(G_{1})$.

##  3 Proof for Double Loop Graph (2-jump Circulant Graph)

In this section, we will give an upper bound on the inducibility of a family
of double loop graphs. The family of double loop graphs contains symmetrical
properties similar to cycles $C_{n}$, which makes it a natural choice of
graphs. We first provide some necessary definitions that will be used in the
proof.

######  Definition 5 (Chain graph $L_{k}$).

We recursively define a chain graph $L_{k}$ as follows. The graph $L_{0}$ is
the triangle with vertices $v_{0},v_{1}$ and $v_{2}$. A chain graph $L_{k}$ is
a chain of triangles formed by connecting $L_{k-1}$ to a new vertex $v_{k+2}$
to the edge $\\{v_{k},v_{k+1}\\}$, for $k>0$.

$v_{1}$$v_{0}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$L_{0}$$L_{1}$ Figure 2: An
illustration of a chain graph $L_{4}$ on 7 vertices. $L_{0}$ is the triangle
graph circled in blue, while the chain graph $L_{1}$ is circled in red.

We provide the following definitions for a _good tuple_ , _loopy $k$-tuple_
and a _good prefix_ :

######  Definition 6 (Good tuple).

We define a good tuple of order $l>0$ recursively. For $l\leq 3$, the ordered
sequence of vertices (ordered tuple), $(v_{0},v_{1},\ldots,v_{l-1})$ is a good
tuple if it induces the complete graph $K_{l}$. For any $l>3$, the ordered
tuple $(v_{0},v_{1},\ldots,v_{l-1})$ is a good tuple if it induces the chain
graph $L_{l-3}$ and the ordered tuple $(v_{0},v_{1},\ldots,v_{l-2})$ is a good
tuple.

######  Definition 7 (Loopy $k$-tuple).

A loopy $k$-tuple is an ordered sequence of vertices
$(v_{0},v_{1},\ldots,v_{k-1})$ which induces a copy of the double loop graph
of order $k$, and for $l<k-1$, every ordered tuple
$(v_{0},v_{1},\ldots,v_{l})$ is a good tuple.

######  Definition 8 (Good prefix).

An ordered tuple $(v_{0},v_{1},\ldots v_{l-1})$ of length $l\leq k$ is a good
prefix, if it is a good tuple of length $l<k$, or a loopy $k$-tuple.

We state the following theorem.

######  Theorem 4.

Every graph on $n$ vertices contain at most $\dfrac{27n^{k}}{k^{k}}$ induced
copies of the double loop graph $DLG(1,2)$ for $k\geq 5$.

###### Proof.

Suppose we have a graph $G$ of $n$, and an integer $k\geq 5$. We will count
the number of loopy $k$-tuples in the graph $G$. We define the probability
distribution $P(D)$ based on conditional probability for each loopy $k$-tuple
$D=\left(v_{0},v_{1},\ldots,v_{k-1}\right)$ as

$P(D)=\prod^{k-1}_{i=0}P_{i}(v_{i}|v_{i-1}).$ (10)

Let $n_{i}$ denote the number of choices for $v_{i}$ given
$(v_{0},\ldots,v_{i-1})$ is a good prefix. We denote the probability
$P_{i}(v_{i}|(v_{0},\ldots,v_{i-1}))=\frac{1}{n_{i}}$. When $i=0$, we can
choose any vertex and so

$P_{0}(v_{0})=\frac{1}{n_{0}}=\frac{1}{n}.$

For $1\leq i\leq k$, the choice for $v_{i}$ must ensure that
$(v_{0},\ldots,v_{i-1})$ is a _good prefix_ and the probability for each
$P_{i}(v_{i})$ is dependent on the choices of the vertices
$v_{0},\ldots,v_{i-1}.$

When $i=1,2$, we have

$\displaystyle P_{1}(v_{1})$
$\displaystyle=\frac{1}{n_{1}}=\frac{1}{deg(v_{0})},$ $\displaystyle
P_{2}(v_{2})$
$\displaystyle=\frac{1}{n_{2}}=\frac{1}{|N(v_{0})|\cap|N(v_{1})|}$

where $N(v)$ denotes the neighbours of $v$.

The vertex $v_{k-1}$ can be chosen if and only if the vertex $v_{k-1}$ is
adjacent to vertices $v_{k-2},v_{k-3},v_{0}$ and $v_{1}$, but not adjacent to
any other vertex belonging to the ordered tuple.

Recall that a _good prefix_ is an ordered tuple of length $l\leq k$. If a
maximal good prefix has length $k$, then it gives a loopy $k$-tuple. If a good
tuple of length $l<k$ can not be further extended to a loopy $k$-tuple, then
the good tuple is a maximal good prefix. We state the following lemma for the
probability distribution $P(D)$.

######  Lemma 1.

The probability distribution $P(D)$ of all loopy $k$-tuples $D$ has a sum of
at most 1.

Consider the vertices that induce a $DLG(1,2)$ such that the loopy $k$-tuple
$D_{j}$ is of the sequence ($v_{j}v_{j+1}v_{j+2}\ldots v_{j+k-1}$) for
$j=0,1,\ldots,k-1$, indices $\bmod$ $k$. We want to show that

$\dfrac{k^{k}}{54n^{k}}\leq P(D_{0})+\ldots+P(D_{k-1}).$ (11)

Each $D_{j}$ corresponds to 2 loopy $k$-tuples namely
$v_{j}v_{j+1}v_{j+2}\ldots v_{j+k-1}$ and $v_{j+k-1}v_{j+k-2}v_{j+k-3}\ldots
v_{j}$. Thus, we have a total of $2k$ loopy $k$-tuples for each induced
$DLG(1,2)$. Thus, (11) would imply that the sum of these $2k$ loopy $k$-tuples
is at least $\dfrac{k^{k}}{27n^{k}}$. It follows from Lemma 1 that there are
at most $\dfrac{27n^{k}}{k^{k}}$ induced $DLG(1,2)$. To prove (11), consider
the AM-GM inequality, such that

$\dfrac{P(D_{0})+P(D_{1})+P(D_{2})+\ldots+P(D_{k-1})}{k}\geq\left(\prod^{k-1}_{j=0}P(D_{j})\right)^{\frac{1}{k}}.$
(12)

Let $n_{i,j}$ be the number of choices for $v_{i}$ in $D_{j}$. Note,
$n_{0,j}=n$ for all $j$. Recall that for $i=2,\ldots,k-2$, a vertex $v_{i}$ is
chosen from the neighbours of vertex $v_{i-1}$ given that
$v_{0}v_{1}v_{2}\ldots v_{i-1}$ is a good prefix. The last vertex $v_{k-1}$ is
chosen if it is only adjacent to $v_{k-2},v_{1},v_{2}$ and $v_{0}$, but not
adjacent to any other vertex that belongs in the good tuple. We take the
right-hand side of the inequality (12) to get the following,

$\displaystyle\left(\prod^{k-1}_{j=0}\dfrac{1}{P(D_{j})}\right)^{\frac{1}{k(k-1)}}$
$\displaystyle=\prod^{k-1}_{j=0}\left(n_{0,j}\frac{n_{1,j}}{3}\frac{n_{2,j}}{3}{n_{3,j}}\ldots
n_{k-2,j}\frac{n_{k-1,j}}{3}\right)^{\frac{1}{k(k-1)}}$ (13)

Let $v^{\prime}$ be a potential candidate for $v_{i}$ and consider the
contributions of $v^{\prime}$ to each of the $n_{i,j}$ term for each
$j=0,1,\ldots,k-1$. Due to the symmetrical properties of $DLG(1,2)$, we need
only consider the case for $j=0$.

We know that $n_{0,j}=n$ for all $j$ by definition. Similarly, we know that
each tuple $D_{j}$ contributes to 2 loopy $k$-tuples. Now let $l>i$ be the
smallest integer in $[0,k)$ such that $v^{\prime}$ is adjacent to $v_{i}$ and
$v_{l}$, and $\\{v_{i},v_{l}\\}$ gives an edge that belongs to the ordered
tuple $(v_{0},v_{1},\ldots,v_{k-1})$.

If $i=0$ and $l=1$, then $v^{\prime}$ contributes to each $n_{1,0}$, $n_{2,0}$
and $n_{k-1,0}$, giving the terms $\frac{n_{1,j}}{3},\frac{n_{2,j}}{3}$ and
$\frac{n_{k-1,j}}{3}$ from equation (13). Thus,

$\displaystyle\left(\prod^{k-1}_{j=0}\dfrac{1}{P(D_{j})}\right)^{\frac{1}{k(k-1)}}$
$\displaystyle=\left((2\cdot
n\cdot(3^{3}))^{k}\prod^{k-1}_{j=0}\frac{n_{1,j}}{3}\frac{n_{2,j}}{3}n_{3.j}\cdots
n_{k-2,j}\frac{n_{k-1,j}}{3}\right)^{\frac{1}{k(k-1)}}$ (14)
$\displaystyle=(54n)^{\frac{1}{k-1}}\left(\prod^{k-1}_{j=0}\frac{n_{1,j}}{3}\frac{n_{2,j}}{3}n_{3.j}\cdots
n_{k-2,j}\frac{n_{k-1,j}}{3}\right)^{\frac{1}{k(k-1)}}$ (15) From equation
(12),
$\displaystyle\left(\prod^{k-1}_{j=0}\dfrac{1}{P(D_{j})}\right)^{\frac{1}{k(k-1)}}$
$\displaystyle\leq\dfrac{(54n)^{\frac{1}{k-1}}}{k(k-1)}\left(\sum^{k-1}_{j=0}\left(\frac{n_{1,j}}{3}+\frac{n_{2,j}}{3}+{n_{3,j}}+\ldots+n_{k-2,j}+\frac{n_{k-1,j}}{3}\right)\right)$
(17)

For all $i>0$, if $l=i+1$, $v^{\prime}_{i}$ contributes to $n_{i+2,0}$.
However, if $l>i+1$, then $v^{\prime}$ does not contribute to the sum for any
$j$. Considering all possible cases, $v^{\prime}$ contributes at most 1 for
every $j$. Thus, $v^{\prime}$ adds at most $k$ to the total sum in (17). As
there are $n$ vertices in the graph $G$, each vertex $v^{\prime}\in V(G)$
contributes at most 1 to the sum in (17), making the whole sum at most $n\cdot
k$. We derive the upper bound (Equation 17) from Equation
LABEL:eq:amgmequality using the AM-GM inequality, and it follows that

$\displaystyle\left(\prod^{k-1}_{j=0}\dfrac{1}{P(D_{j})}\right)^{\frac{1}{k(k-1)}}$
$\displaystyle\leq\dfrac{(54n)^{\frac{1}{k-1}}}{k(k-1)}\cdot n\cdot
k=\dfrac{(54n)^{\frac{1}{k-1}}\cdot n\cdot k}{k(k-1)}$ (18) Which then gives
$\displaystyle\left(\prod^{k-1}_{j=0}\dfrac{1}{P(D_{j})}\right)^{\frac{1}{k}}$
$\displaystyle\leq\dfrac{54n^{k}}{(k-1)^{k-1}}$ (19) Thus,
$\displaystyle\left(\prod^{k-1}_{j=0}P(D_{j})\right)^{\frac{1}{k}}$
$\displaystyle\geq\dfrac{(k-1)^{k-1}}{54n^{k}}.$ (20)

∎

###  3.1 Further Results for $k$

In this section, we introduce constructions for the $DLG(1,2)$ graph to obtain
a lower bound for some $k$. First, notice that when $k=5$, the $DLG(1,2)$ is
the complete graph $K_{n}$ of order 5. Using the upper bound obtained in
equation (7), we obtain the following lemma:

######  Lemma 2.

The inducibility of $DLG(1,2)$ is given by
$\mathcal{I}(DLG(1,2))\leq\dfrac{27k!}{k^{k}}$.

By Lemma 2, we obtain $\mathcal{I}(DLG(1,2))\leq 1\frac{23}{625}\approx
1.0368$ for $k=5$. This gives a close result to the known result for
inducibility of complete graphs $\mathcal{I}(K_{5})=1$.

For the case where $k=6$, we give a construction that gives a lower bound to
the inducibility $\mathcal{I}(DLG(1,2))\geq\frac{10}{81}$. This result brings
the gap between the upper bound and the lower bound to a factor of $3$. Our
construction uses a partitioning method for $DLG(1,2)$ for $k=6$ and is as
follows: Consider a subgraph $C_{4}$ of a $DLG(1,2)$.

We take 3 partitions $P_{1},P_{2},P_{3}$ such that each partition contains $n$
vertices. The partitions $P_{1}$ and $P_{2}$ give a complete bipartite graph
$K_{n,n}$ and $P_{3}$ is the set of isolated vertices which are connected to
all vertices in $P_{1}$ and $P_{2}$. From each partition, we pick two
vertices. The graph induced by these six vertices is $DLG(1,2)$. Thus,

$\displaystyle\mathcal{P}(DLG(1,2),n)$
$\displaystyle=\binom{n}{2}\cdot\binom{n}{2}\cdot\binom{n}{2}=\dfrac{n^{3}(n-1)^{3}}{8}.$
(21)

Now, from Equation (21), we have:

$\displaystyle\dfrac{\dfrac{n^{3}(n-1)^{3}}{8}}{\binom{3n}{6}}$
$\displaystyle=\dfrac{n^{3}(n-1)^{3}}{8}\cdot\dfrac{6!}{3n(3n-1)(3n-2)(3n-3)(3n-4)(3n-5)}.$

Taking the limit as $N$ approaches $\infty$, we obtain the lower bound on the
inducibility of $DLG(1,2)$

$\displaystyle\mathcal{I}(DLG(1,2))$ $\displaystyle\approx\dfrac{6!\cdot
n^{6}}{3^{6}n^{6}}=\dfrac{10}{81}.$ (22)

Recall that a graph $G$ and it’s complement share the same inducibility, that
is $\mathcal{I}(G)=\mathcal{I}({\overline{G}})$. The complement of the
$DLG(1,2)$ on $k=6$ gives 3 disjoint $K_{2}$s. To compare our results with the
bound using Theorem 9, we construct $G$ and $G^{\prime}$ as follows. Take two
of the disjoint $K_{2}$s as $G$ and the other $K_{2}$ as a graph $G^{\prime}$.
We know that $\overline{G}=C_{4}$ and $\overline{G^{\prime}}=N_{2}$. Take
$k=4$ and $k^{\prime}=2$, computing inducibility using the bound from Theorem
9 we have:

$\displaystyle\mathcal{I}(G\wedge G^{\prime})$
$\displaystyle\geq\dfrac{6!\cdot 4^{4}\cdot 2^{2}}{4!\cdot 2!\cdot
6^{6}}\cdot\frac{3}{8}\cdot 1=\frac{10}{81}$

which gives the same result as (22).

Now for the case $k=7$ for $DLG(1,2)$, we consider the complement
$\overline{DLG(1,2)}$ which is precisely the cycle $C_{7}$. The known
conjecture for cycles was given by Pippenger and Golumbic [56], where
$\mathcal{I}(C_{k})\geq\dfrac{k!}{k^{k}-k}$ for $k\geq 5$. Further, Král et
al. [44] proved an upper bound for $k\geq 6$ where
$\mathcal{I}(C_{k})\leq(2+o(1))\cdot\frac{k!}{k^{k}}$. The current best
construction known for $C_{k}$ is the nested blow-up of a $C_{k}$. Thus, for
the $\overline{DLG(1,2)}$ for $k=7$, the inducibility is calculated as:

$\mathcal{I}(C_{7})=\mathcal{I}(DLG(1,2))\geq\frac{5}{817}.$

Using the upper bound from our construction we obtain
$\mathcal{I}{(DLG(1,2))}\leq 0.165237$, which gives a factor of 27 to our
upper bound.

##  4 Conclusion

In this paper, we presented a proof for the upper bound on the inducibility of
the family of double loop graphs $DLG(1,2)$ in a given graph $G$. For the case
when $k=5$, we showed that our upper bound is indeed close to the known
inducibility of $K_{5}$, where $\mathcal{I}(K_{5})=1$. We further showed the
lower bound for the counts of $DLG(1,2)$ for $k=6$. We presented a
construction for the $DLG(1,2)$. When compared to the bound given by Pippenger
and Golumbic [56] for disjoint graphs, we showed that our construction is in
fact the best possible construction that maximises the number of $DLG(1,2)$ in
any given graph $G$.

Future work include finding the lower bound for this class of graphs for
$k\geq 8$. We may also consider finding the bounds on the inducibility for the
family of graphs that have some symmetrical properties.

## References

  * Alspach and Parsons [1979] B. Alspach and T.D. Parsons.  Isomorphism of circulant graphs and digraphs.  _Discrete Math._ , 25(2):97–108, 1979.
  * Babai [1979] L. Babai.  Spectra of Cayley graphs.  _J. Combin. Theory, Series B_ , 27:180–189, 1979.
  * Balogh et al. [2016] J. Balogh, P. Hu, B. Lidick, and F. Pfender.  Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle.  _European J. Combin._ , 52:47–58, 2016.
  * Bernasconi and Codenotti [1999] A. Bernasconi and B. Codenotti.  Spectral analysis of Boolean functions as a graph eigenvalue problem.  _IEEE Trans. Comput._ , 48(3):345–351, 1999.
  * Blumenthal and Phillips [2021] A. Blumenthal and M. Phillips.  Inducibility of the net graph.  _arXiv_ , 2021.
  * Boesch and Tindell [1984] F. Boesch and R. Tindell.  Circulants and their connectivities.  _J. Graph Theory_ , 8(4):487–499, 1984.
  * Bogdanowicz [2015] Z.R. Bogdanowicz.  Decomposition of circulant digraphs with two jumps into cycles of equal lengths.  _Discrete Appl. Math._ , 180:45–51, 2015.
  * Bollobás [1976] B. Bollobás.  On complete subgraphs of different orders.  In _Math. Proc. Cambridge Philos. Soc._ , volume 79, pages 19–24, 1976.
  * Bonfert-Taylor et al. [2011] P. Bonfert-Taylor, R.D. Canary, J. Souto, and E.C. Taylor.  Exotic quasi-conformally homogeneous surfaces.  _Bull. London Math. Soc._ , 43:57–62, 2011.
  * Bozejko et al. [2006] M. Bozejko, K. Dykema, and F. Lehner.  Isomorphisms of Cayley graphs of surface groups.  _Algebra Discrete Math._ , 5(1):18–36, 2006.
  * Brown and Sidorenko [1994] J.I. Brown and A. Sidorenko.  The inducibility of complete bipartite graphs.  _J. Graph Theory_ , 6(18):629–645, 1994.
  * Buser [1988] P. Buser.  Cayley graphs and planar isospectral domains.  In _Geometry and Analysis on Manifolds_ , pages 64–77. Springer-Verlag, Berlin, 1988.
  * Cai et al. [1999] J.Y. Cai, G. Havas, B. Mans, A. Nerurkar, J.P. Seifert, and I. Shparlinksi.  On routing in circulant graphs.  In _Computing and Combinatorics_ , pages 360–369, 1999.
  * Camelo et al. [2014] M. Camelo, D. Papadimitriou, L.Fàbrega, and P. Vilà.  Efficient routing in data centerwith underlying Cayley graph.  _Complex Networks V_ , pages 189–197, 2014.
  * Choi et al. [2020] I. Choi, B. Lidický, and F. Pfender.  Inducibility of directed paths.  _Discrete Math._ , 343(10):1–11, 2020.
  * Couvreur et al. [2013] A. Couvreur, N. Delfosse, and G. Zemor.  A construction of quantum LDPC codes from Cayley graphs.  _IEEE Trans. Inf. Theory_ , 59(9):6087–6098, 2013\.
  * Cunha and Protti [2018] L. Cunha and F. Protti.  Closure of genomic sets: applications of graph convexity to genome rearrangement problems.  _Electron. Notes Discrete Math._ , 69:285–292, 2018.
  * Cunha and Protti [2019] L. Cunha and F. Protti.  Genome rearrangements on multigenomic models: Applications of graph convexity problems.  _Journal of Comput. Biol._ , 26(11):1214–1222, 2019.
  * Czabarka et al. [2020] É. Czabarka, A.A.V. Dossou-Olory, L.A. Székely, and S. Wagner.  Inducibility of $d$-ary trees.  _Discrete Math._ , 343(2):1–15, 2020.
  * Dossou-Olory [2018] A.A.V. Dossou-Olory.  _On the Inducibility of Rooted Trees_.  PhD thesis, Stellenbosch Univer., 2018.
  * Egri-Nagy et al. [2014] A. Egri-Nagy, A.R. Francis, and V. Gebhardt.  Bacterial genomics and computational group theory: The BIOGAP package for GAP.  In _ICMS 2014_ , pages 67–74, 2014.
  * Erdös [1969] P. Erdös.  On the number of complete subgraphs and circuits contained in graphs.  _Časopis pro Pěstování Matematiky_ , 94(3):290–296, 1969.
  * Even-Zohar and Linial [2015] C. Even-Zohar and N. Linial.  A note on the inducibility of 4-vertex graphs.  _Graphs Combin._ , 31(5):1367–1380, 2015.
  * Exoo [1986] G. Exoo.  Dense packing of induced subgraphs.  _Ars Combin._ , (22):5–10, 1986.
  * Fox et al. [2015] J. Fox, H. Huang, and C. Lee.  On the inducibility problem for almost all graphs.  _Manuscript/Preprint_ , 2015.
  * Fox et al. [2021] J. Fox, L. Sauermann, and F. Wei.  On the inducibility problem for random Cayley graphs of abelian groups with a few deleted vertices.  _Random Structures Algorithms_ , 59(4):554–615, 2021.
  * Francis and Wynn [2020] A.R. Francis and H.P. Wynn.  A mean first passage time genome rearrangement distance.  _J. Math. Biol._ , 80:1971–1992, 2020.
  * Godsil [2012] C. Godsil.  State transfer on graphs.  _Discrete Math._ , 312(1):129,147, 2012.
  * Gómez et al. [2005] D. Gómez, J. Gutierrez, A. Ibeas, C. Martínez, and R. Beivide.  On finding a shortest path in circulant graphs with two jumps.  In _Comput. Combin._ , pages 777–786, 2005.
  * Gómez et al. [2007] D. Gómez, J. Gutierrez, and A. Ibeas.  Optimal routing in double loop networks.  _Theoret. Comput. Sci._ , 381:68–85, 2007.
  * Gu and Hao [2018] M. Gu and R.X. Hao.  Reliability analysis of Cayley graphs generated by transpositions.  _Discrete Appl. Math._ , 244(31):94–102, 2018\.
  * Hatami et al. [2014] H. Hatami, J. Hirst, and S. Norine.  The inducibility of blow-up graphs.  _J. Combin. Theory Ser. B_ , 109:196–212, 2014.
  * Hefetz and Tyomkyn [2017] D. Hefetz and M. Tyomkyn.  On the inducibility of cycles.  _Electron. Notes Discrete Math._ , 61:593–599, 2017.
  * Hellmuth et al. [2020] M. Hellmuth, D. Merkle, and N. Nøjgaard.  Atom tracking using Cayley graphs.  In _Bioinformatics Research and Applications_ , pages 406–415, 2020\.
  * Heydemann [1997] M.C. Heydemann.  Cayley graphs and interconnection networks.  In _Graph Symmetry_ , volume 497, pages 167–224. Springer-Dordrecht, 1997.
  * Hirst [2011] J. Hirst.  The inducibility of graphs on four vertices.  _J. Graph Theory_ , 75(3):1–12, 2011.
  * Hsieh and Hsiao [2005] S.Y. Hsieh and T.T. Hsiao.  The $k$-degree Cayley graph and its topological properties.  _Networks_ , 47(1):26–36, 2005.
  * Huang [2014] H. Huang.  On the maximum induced density of directed stars and related problem.  _SIAM J. Discrete Math._ , 28(1):92–98, 2014\.
  * Imran et al. [2012] M. Imran, A.Q. Baig, S.A.U.H. Bokhary, and I. Javaid.  On the metric dimension of circulant graphs.  _Appl. Math. Lett._ , 25(3):320–325, 2012.
  * Jiang et al. [2019] Y. Jiang, X. Ge, Y. Zhong, G. Mao, and Y. Li.  A new small-world IoT routing mechanism based on Cayley graphs.  _IEEE IoT_ , 6(6):10384–10395, 2019.
  * Joslin et al. [2021] S.S. Joslin, P.C. Kainen, and S. Overbay.  On dispersability of some circulant graphs.  _arXiv_ , pages 1–17, 2021.
  * Kaufmann and Zweig [2009] M. Kaufmann and K. Zweig.  Modeling and designing real–world networks.  In _Algorithmics of Large and Complex Networks_ , pages 359–379. Springer, 2009.
  * Knor et al. [2019] M. Knor, R. Škrekovski, and A. Tepeh.  Chemical graphs with the minimum value of Wiener index.  _MATCH-Commun. Math. Co._ , 81:119–132, 2019.
  * Král et al. [2019] D. Král, S. Norin, and J. Volec.  A bound on the inducibility of cycles.  _J. Combin. Theory Ser. A_ , 161:359–363, 2019.
  * Li and Li [1998] Q. Li and Q. Li.  Reliability analysis of circulant graphs.  _Networks_ , 31(2):61–65, 1998.
  * Li and Meng [2008] R. Li and J. Meng.  Reversals Cayley graphs of symmetric groups.  _Inform. Process. Lett._ , 109:130–132, 2008.
  * Liu et al. [2009] H. Liu, L.M. Zhang, and B. Zeng.  Groupnet: A novel P2P grouping network based on Cayley graph.  In _APCIP 2009_ , volume 2, pages 557–561, 2009.
  * Lu [2016] R. Lu.  Fast methods for designing circulant network topology with high connectivity and survivability.  _JoCCASA_ , 5(5):1–13, 2016.
  * Mokhtar [2017] H. Mokhtar.  A few families of Cayley graphs and their efficiency as communication networks.  _Bull. Aust. Math. Soc._ , 95:518–520, 2017.
  * Moulton and Steel [2012] V. Moulton and M. Steel.  The ‘butterfly effect’ in Cayley graphs with applications to genomics.  _J. Math. Biol._ , 65:1267–1284, 2012.
  * Munir et al. [2016] M. Munir, W. Nazeer, Z. Shahzadi, and S. M. Kang.  Some invariants of circulant graphs.  _Symmetry_ , 8(11):1–8, 2016.
  * Muzychuk [1997] M. Muzychuk.  On Ádám’s conjecture for circulant graphs.  _Discrete Math._ , 176:285–298, 1997.
  * Nøjgaard et al. [2021] N. Nøjgaard, W. Fontana, M. Hellmuth, and D. Merkle.  Cayley graphs of semigroups applied to atom tracking in chemistry.  _J. Comput. Biol._ , 28(7):1–28, 2021.
  * Obradoviç et al. [2005] N. Obradoviç, J. Peters, and G. Ružić.  Reliable broadcasting in double loop networks.  _Networks_ , 46(2):88–97, 2005.
  * Pérez-Rosés et al. [2022] H Pérez-Rosés, M. Bras-Amorós, and J.M. Serradilla-Merinero.  Greedy routing in circulant networks.  _Graphs Combin._ , 38(3), 2022.
  * Pippenger and Golumbic [1975] N. Pippenger and M.C. Golumbic.  The inducibility of graphs.  _J. Combin. Theory Ser. B_ , 19(3):189–283, 1975\.
  * Pourfaraj and Ghorbani [2020] L. Pourfaraj and M. Ghorbani.  On the Cayley graphs of Boolean functions.  _Facta Universitatis Series: Mathematics and Informatics_ , 35(3):873–885, 2020.
  * Qin et al. [2009] Y. Qin, W. Xiao, and Š. Miklavič.  Connected graphs as subgraphs of Cayley graphs: Conditions on hamiltonicity.  _Discrete Math._ , 309(17):5426–5431, 2009.
  * [59] A.A. Razborov.  Flag algebras.  _J. Symb. Log._ , 72(4):1239–1282.
  * Riera et al. [2018] C. Riera, P. Solé, and P. Stǎnicǎ.  A complete characterization of plateaued Boolean functions in terms of their Cayley graphs.  In _Progress in Cryptology (AFRICACRYPT 2018)_ , pages 3–8, 2018\.
  * Robič and Žerovnik [2000] B. Robič and J. Žerovnik.  Minimum 2-terminal routing in 2-jump circulant graphs.  _Comput. Inform._ , 19(1):37–46, 2000.
  * Romanov et al. [2020] A.Y. Romanov, E.V. Lezhnev, A.Y. Glukhikh, and A.A. Amerikanov.  Development of routing algorithms in networks-on-chip based on two-dimensional optimal circulant topologies.  _Heliyon_ , 6(1):1–8, 2020.
  * Shahzamanian et al. [2010] M.H. Shahzamanian, M. Shirmohammadi, and B. Davvaz.  Roughness in Cayley graphs.  _Inform. Sci._ , 180(17):3362–3372, 2010.
  * Shparlinski [2006] I. Shparlinski.  On the energy of some circulant graphs.  _Linear Algebra Appl._ , 414(1):378–382, 2006\.
  * Song and Wang [2011] S. Song and D. Wang.  Reliability analysis of the Cayley graphs of dihedral groups.  _Tsinghua Sci. Technol._ , 16(1):36–40, 2011\.
  * Thomason [1997] A. Thomason.  Graph products and monochromatic multiplicities.  _Combinatorica_ , 17(1):125–134, 1997.
  * Tomic [2013] R.V. Tomic.  Optimal networks from error correcting codes.  _ACNS_ , pages 169–179, 2013.
  * Tucker [1983] T. W. Tucker.  Finite groups acting on surfaces and the genus of a group.  _J. Combin. Theory, Series B_ , 34:82–98, 1983.
  * Vadapalli and Srimani [1995] P. Vadapalli and P.K. Srimani.  Trivalent Cayley graphs for interconnection networks.  _Inform. Process. Lett._ , 54(6):329–335, 1995\.
  * Vadapalli and Srimani [1996] P. Vadapalli and P.K. Srimani.  A new family of Cayley graph interconnection networks of constant degree four.  _IEEE Trans. Parallel Distrib. Syst._ , 7(1):26–32, 1996.
  * Vandermolen and Wright [2022] R.R. Vandermolen and D. Wright.  Graph-theoretic approach to quantum error correction.  _Physics Review A_ , 105(3):1–11, 2022.
  * Vaughan [2012] E.R. Vaughan.  Flagmatic.  2012\.
  * Xu et al. [2017] L. Xu, S. Zhou, G. Lian, and Z. Luo.  A kind of conditional connectivity of Cayley graphs generated by 2-trees.  _Comput. J._ , 61(5):714–721, 2017.
  * Yuster [2019] R. Yuster.  On the exact maximum induced density of almost all graphs and their inducibility.  _J. Combin. Theory Ser. B_ , 136:81–109, 2019.
  * Zémor [2009] G. Zémor.  On Cayley graphs, surface codes, and the limits of homological coding for quantum error correction.  In _IMACC (IWCC 2009)_ , volume 5557, pages 259–273, 2009.
  * Zhao et al. [2020] S. L. Zhao, J. M. Chang, and R. X. Hao.  Reliability assessment of the Cayley graph generated by trees.  _Discrete Appl. Math._ , 287:10–14, 2020.