\documentclass[12pt,titlepage]{article} \usepackage{amsmath} \usepackage{mathrsfs} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} \usepackage{mathtools} \usepackage{graphicx} \usepackage{color} \usepackage{ucs} \usepackage[utf8x]{inputenc} \usepackage{xparse} \usepackage{hyperref} %----Macros---------- % % Unresolved issues: % % \righttoleftarrow % \lefttorightarrow % % \color{} with HTML colorspec % \bgcolor % \array with options (without options, it's equivalent to the matrix environment) % Of the standard HTML named colors, white, black, red, green, blue and yellow % are predefined in the color package. Here are the rest. \definecolor{aqua}{rgb}{0, 1.0, 1.0} \definecolor{fuschia}{rgb}{1.0, 0, 1.0} \definecolor{gray}{rgb}{0.502, 0.502, 0.502} \definecolor{lime}{rgb}{0, 1.0, 0} \definecolor{maroon}{rgb}{0.502, 0, 0} \definecolor{navy}{rgb}{0, 0, 0.502} \definecolor{olive}{rgb}{0.502, 0.502, 0} \definecolor{purple}{rgb}{0.502, 0, 0.502} \definecolor{silver}{rgb}{0.753, 0.753, 0.753} \definecolor{teal}{rgb}{0, 0.502, 0.502} % Because of conflicts, \space and \mathop are converted to % \itexspace and \operatorname during preprocessing. % itex: \space{ht}{dp}{wd} % % Height and baseline depth measurements are in units of tenths of an ex while % the width is measured in tenths of an em. \makeatletter \newdimen\itex@wd% \newdimen\itex@dp% \newdimen\itex@thd% \def\itexspace#1#2#3{\itex@wd=#3em% \itex@wd=0.1\itex@wd% \itex@dp=#2ex% \itex@dp=0.1\itex@dp% \itex@thd=#1ex% \itex@thd=0.1\itex@thd% \advance\itex@thd\the\itex@dp% \makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}} \makeatother % \tensor and \multiscript \makeatletter \newif\if@sup \newtoks\@sups \def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}% \def\reset@sup{\@supfalse\@sups={}}% \def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else% \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}% \else \append@sup#2 \@suptrue \fi% \expandafter\mk@scripts\fi} \def\tensor#1#2{\reset@sup#1\mk@scripts#2_/} \def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2% \reset@sup\mk@scripts#3_/} \makeatother % \slash \makeatletter \newbox\slashbox \setbox\slashbox=\hbox{$/$} \def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$} \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa \copy\slashbox \kern-\@tempdima \box\@tempboxa} \def\slash{\protect\itex@pslash} \makeatother % math-mode versions of \rlap, etc % from Alexander Perlis, "A complement to \smash, \llap, and lap" % http://math.arizona.edu/~aprl/publications/mathclap/ \def\clap#1{\hbox to 0pt{\hss#1\hss}} \def\mathllap{\mathpalette\mathllapinternal} \def\mathrlap{\mathpalette\mathrlapinternal} \def\mathclap{\mathpalette\mathclapinternal} \def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}} \def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}} \def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}} % Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2} \let\oldroot\root \def\root#1#2{\oldroot #1 \of{#2}} \renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}} % Manually declare the txfonts symbolsC font \DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n} \SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n} \DeclareFontSubstitution{U}{txsyc}{m}{n} % Manually declare the stmaryrd font \DeclareSymbolFont{stmry}{U}{stmry}{m}{n} \SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n} % Manually declare the MnSymbolE font \DeclareFontFamily{OMX}{MnSymbolE}{} \DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n} \SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n} \DeclareFontShape{OMX}{MnSymbolE}{m}{n}{ <-6> MnSymbolE5 <6-7> MnSymbolE6 <7-8> MnSymbolE7 <8-9> MnSymbolE8 <9-10> MnSymbolE9 <10-12> MnSymbolE10 <12-> MnSymbolE12}{} % Declare specific arrows from txfonts without loading the full package \makeatletter \def\re@DeclareMathSymbol#1#2#3#4{% \let#1=\undefined \DeclareMathSymbol{#1}{#2}{#3}{#4}} \re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116} \re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117} \re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118} \re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119} \re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46} \re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121} \re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12} \re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64} \re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6} \re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77} \re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77} \makeatother % \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE \makeatletter \def\Decl@Mn@Delim#1#2#3#4{% \if\relax\noexpand#1% \let#1\undefined \fi \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}} \def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}} \def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}} \Decl@Mn@Open{\llangle}{mnomx}{'164} \Decl@Mn@Close{\rrangle}{mnomx}{'171} \Decl@Mn@Open{\lmoustache}{mnomx}{'245} \Decl@Mn@Close{\rmoustache}{mnomx}{'244} \makeatother % Widecheck \makeatletter \DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}} \def\@widecheck#1#2{% \setbox\z@\hbox{\m@th$#1#2$}% \setbox\tw@\hbox{\m@th$#1% \widehat{% \vrule\@width\z@\@height\ht\z@ \vrule\@height\z@\@width\wd\z@}$}% \dp\tw@-\ht\z@ \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@ \setbox\tw@\hbox{% \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box \tw@}}}% {\ooalign{\box\tw@ \cr \box\z@}}} \makeatother % \mathraisebox{voffset}[height][depth]{something} \makeatletter \NewDocumentCommand\mathraisebox{moom}{% \IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{% \IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}% }{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}% \mathpalette\@temp{#4}} \makeatletter % udots (taken from yhmath) \makeatletter \def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.} \mkern2mu\raise4\p@\hbox{.}\mkern1mu \raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}} \makeatother %% Fix array \newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}} %% \itexnum is a noop \newcommand{\itexnum}[1]{#1} %% Renaming existing commands \newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}} \newcommand{\widevec}{\overrightarrow} \newcommand{\darr}{\downarrow} \newcommand{\nearr}{\nearrow} \newcommand{\nwarr}{\nwarrow} \newcommand{\searr}{\searrow} \newcommand{\swarr}{\swarrow} \newcommand{\curvearrowbotright}{\curvearrowright} \newcommand{\uparr}{\uparrow} \newcommand{\downuparrow}{\updownarrow} \newcommand{\duparr}{\updownarrow} \newcommand{\updarr}{\updownarrow} \newcommand{\gt}{>} \newcommand{\lt}{<} \newcommand{\map}{\mapsto} \newcommand{\embedsin}{\hookrightarrow} \newcommand{\Alpha}{A} \newcommand{\Beta}{B} \newcommand{\Zeta}{Z} \newcommand{\Eta}{H} \newcommand{\Iota}{I} \newcommand{\Kappa}{K} \newcommand{\Mu}{M} \newcommand{\Nu}{N} \newcommand{\Rho}{P} \newcommand{\Tau}{T} \newcommand{\Upsi}{\Upsilon} \newcommand{\omicron}{o} \newcommand{\lang}{\langle} \newcommand{\rang}{\rangle} \newcommand{\Union}{\bigcup} \newcommand{\Intersection}{\bigcap} \newcommand{\Oplus}{\bigoplus} \newcommand{\Otimes}{\bigotimes} \newcommand{\Wedge}{\bigwedge} \newcommand{\Vee}{\bigvee} \newcommand{\coproduct}{\coprod} \newcommand{\product}{\prod} \newcommand{\closure}{\overline} \newcommand{\integral}{\int} \newcommand{\doubleintegral}{\iint} \newcommand{\tripleintegral}{\iiint} \newcommand{\quadrupleintegral}{\iiiint} \newcommand{\conint}{\oint} \newcommand{\contourintegral}{\oint} \newcommand{\infinity}{\infty} \newcommand{\bottom}{\bot} \newcommand{\minusb}{\boxminus} \newcommand{\plusb}{\boxplus} \newcommand{\timesb}{\boxtimes} \newcommand{\intersection}{\cap} \newcommand{\union}{\cup} \newcommand{\Del}{\nabla} \newcommand{\odash}{\circleddash} \newcommand{\negspace}{\!} \newcommand{\widebar}{\overline} \newcommand{\textsize}{\normalsize} \renewcommand{\scriptsize}{\scriptstyle} \newcommand{\scriptscriptsize}{\scriptscriptstyle} \newcommand{\mathfr}{\mathfrak} \newcommand{\statusline}[2]{#2} \newcommand{\tooltip}[2]{#2} \newcommand{\toggle}[2]{#2} % Theorem Environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{prop}{Proposition} \newtheorem{cor}{Corollary} \newtheorem*{utheorem}{Theorem} \newtheorem*{ulemma}{Lemma} \newtheorem*{uprop}{Proposition} \newtheorem*{ucor}{Corollary} \theoremstyle{definition} \newtheorem{defn}{Definition} \newtheorem{example}{Example} \newtheorem*{udefn}{Definition} \newtheorem*{uexample}{Example} \theoremstyle{remark} \newtheorem{remark}{Remark} \newtheorem{note}{Note} \newtheorem*{uremark}{Remark} \newtheorem*{unote}{Note} %------------------------------------------------------------------- \begin{document} %------------------------------------------------------------------- \section*{directed graph} \begin{quote}% This entry is a \emph{disambiguation page}, plus some commentary that would not fit well on either of the pages [[digraph]] and [[quiver]], particularly on related technical terms such as \emph{oriented graph}, \emph{bidirected graph}, and \emph{signed graph}, with their standard meanings in modern combinatorics. \end{quote} \hypertarget{context}{}\subsubsection*{{Context}}\label{context} \hypertarget{graph_theory}{}\paragraph*{{Graph theory}}\label{graph_theory} [[!include graph theory - contents]] \hypertarget{contents}{}\section*{{Contents}}\label{contents} \noindent\hyperlink{overview_of_usual_technical_terms}{Overview of usual technical terms}\dotfill \pageref*{overview_of_usual_technical_terms} \linebreak \noindent\hyperlink{table_of_definitions_of_directed_graphs_in_various_references}{Table of definitions of directed graphs in various references}\dotfill \pageref*{table_of_definitions_of_directed_graphs_in_various_references} \linebreak \noindent\hyperlink{bidirected_graphs}{Bidirected graphs}\dotfill \pageref*{bidirected_graphs} \linebreak \noindent\hyperlink{connections_to_category_theory}{Connections to category theory}\dotfill \pageref*{connections_to_category_theory} \linebreak \noindent\hyperlink{underlying_quivers}{Underlying quivers}\dotfill \pageref*{underlying_quivers} \linebreak \noindent\hyperlink{an_application_of_directed_graphs_to_category_theory}{An application of directed graphs to category theory}\dotfill \pageref*{an_application_of_directed_graphs_to_category_theory} \linebreak \noindent\hyperlink{all_quivers_deemed_irreflexive_by_lawvere}{\emph{All} quivers deemed irreflexive by Lawvere}\dotfill \pageref*{all_quivers_deemed_irreflexive_by_lawvere} \linebreak \noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak \noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak The term \emph{directed graph} is used in both [[graph theory]] and [[category theory]]. The definition varies -- even within \emph{one} of the two theories. In [[graph theory]], \emph{directed graph} (often abbreviated to the contraction \emph{digraph}) nowadays usually means a [[digraph]], while in [[category theory]], directed graph generally means a [[quiver]]. The basic difference is: [[quivers]] may have multiple arrows in the \emph{same} direction (often called ``parallel''), and also \emph{loops}, while [[digraphs]] may not have any of those. \hypertarget{overview_of_usual_technical_terms}{}\subsection*{{Overview of usual technical terms}}\label{overview_of_usual_technical_terms} \begin{quote}% We see one family, in the same room but hardly together. The family of signed, gain, and biased graphs is a lot like that. The Bibliography and Glossary are supposed to lead the family members to talk to one another. May they do so! (\hyperlink{HomePageOfSignedGraphs}{Thomas Zaslavsky: front page}) \end{quote} The following table may help distinguish the various terminological conventions in current use: \newline | signed [[graph]] | undirected [[graph]] with a sign on each edge | undirected simple [[graph]] together with a function $\{$edges$\}$ $\rightarrow$ $\{-,+\}$,not subject to any axioms | dependent on the chosen formalization of [[graph|undirected simple graph]]; if [[graph|undirected simple graph]] is formalized in one of the usual ways as a [[relation|symmetric irreflexive relation]], and the signs in the usual way as two [[signature|constant symbols]], then the signature is: [[equality| = ]], one relation symbol, two constant symbols; and the axioms then are: one axiom expressing irreflexivity, one axiom expressing symmetry; note that no axiom to express distinctness of the two constant symbols is necessary, as this, in the usual approach, is built into the signature; if [[constructive logic]] is required, the signature might be larger, requiring an [[apartness relation]] to express irreflexivity | beware that this should \emph{not} in a natural way be regarded a ``directed graph'', though they \emph{are} often used in \emph{contexts} together with directed graphs and thus belong on this page; in a sense, ``signed graphs'' are a non-example, an \emph{odd-one-out}, in particular in that they seem tricky to categorically construct | | bidirected [[graph]] | [[quiver]] with a sign on each vertex-arrow-\emph{[[incidence|incidence relation]]} | quiver together with function $\{$vertices$\}$ $\times$ $\{$arrows$\}$ $\rightarrow$ $\{-,+\}$, subject to axioms | | | Note that there are two points of view in model theory: one regards [[equality| = ]] as a [[logic|logical symbol]] of a meta-language (e.g., first-order logic with equality), the other regards [[equality| = ]] as a binary relation symbol defined within the language under investigation. In the table, as a reminder that equality plays an important role in these theories, the latter view was taken. \hypertarget{table_of_definitions_of_directed_graphs_in_various_references}{}\subsection*{{Table of definitions of directed graphs in various references}}\label{table_of_definitions_of_directed_graphs_in_various_references} This is to give a compressed look-up table, quickly usable, telling you what definition of directed graph is being used in the reference you happen to be working with. \begin{tabular}{l|l|l|l|l} reference&kind of directed graph emphasized in the reference&formalization used; and exact reference to place in reference&\emph{word} used in reference&miscellaneous further comments\\ \hline \hyperlink{DG2nd}{BangJensenGutin2nd}&[[digraph]]&the one in [[digraph]], except for a needless assumption of a vertex-set being non-empty: an empty vertex-set implies that the binary relation is the empty relation, but this \emph{is} a [[digraph]]&\emph{digraph}&beware that that book sometimes treats [[quivers]], but calls them \emph{directed pseudographs} and formalizes those using [[multisets]] of ordered pairs\\ \hyperlink{BondyMurtyFirstEdition}{BondyMurtyt1st}&[[quiver]]&unusually hybrid functional-relational formalization via \emph{families of ordered pairs}&\emph{digraph}; beware that Bondy-Murty-digraphs are \emph{not} [[digraphs]]&aversion to the void: needless assumption of vertex-sets being non-empty; essentially, Bondy-Murty-digraphs$\simeq$Schrijver-digraphs\\ \hyperlink{CLZ2016}{ChartrandLesniakZhang6th}&[[digraph]]&the one in [[digraph]], except for a needless assumption of a digraph being non-empty set: the empty set \emph{is} a [[digraph]]&\emph{digraph}&beware that what the authors call ``The First Theorem of Digraph Theory'' is a \emph{not} a theorem of ``Digraph Theory'' in the strictest technical sense of ``Digraph Theory''($=$the first-order theory of irreflexive binary relations) since it \emph{uses the language of arithmetic}\\ \hyperlink{DecompositionProof}{CsabaEtAl2016}&[[digraph]]&the one in [[digraph]]&\emph{digraph}&\\ \hyperlink{Diestel2010}{DiestelGraphTheory4th}&[[quiver]]&the usual one: cf. \hyperlink{Diestel2010}{Section 1.10}, which is the ``nuts-and-bolts-definition'' in [[quiver]]&\emph{directed graph}; wisely, the contraction \emph{digraph} is used but once in main text, avoiding a clash with [[digraph]]&beware that \emph{directed path} in the book means something different, type-theoretically at least, from \emph{path in a [[digraph]]}: in the book, a \emph{directed path} is itself a [[digraph]], not a sequence of vertices\\ \hyperlink{HararyGraphTheory1969}{HararyGraphTheory1969}&[[digraph]]&the one in [[digraph]]; cf. \hyperlink{HararyGraphTheory1969}{Chapter 16}, provided the word ``collection'' is read ``set'', which, as is abundantly clear from the context, is what Harary means; Harary is unambiguous that he does not allow digraphs to have loops; so Harary-digraphs are [[digraphs]]&\emph{digraph}&Harary uses \hyperlink{HararyGraphTheory1969}{p. 199, second paragraph} the unusual term ``semiwalk'' what is called ``wealk walk'' in [[digraph]]; note \hyperlink{HararyGraphTheory1969}{p. 198, last paragraph} that Harary's ``path'' is (modulo ``paths'' in [[digraph]] not being digraphs but only vertex-sequences) precisely the usual meaning of ``path'', although he only mentions that there be no point-repetitions: this evidently implies that there are no arc-repetitions; in summary, Harary-paths are [[digraph\\ \hyperlink{AnalyticCombinatorics2009}{FlajoletSedgewick1st}&[[binary relation]]&[[binary relations]], formalized in [[material set theory]]-style, cf. \hyperlink{AnalyticCombinatorics2009}{V.5.1}&both \emph{digraph} and \emph{directed graph} used interchangeably&beware that Flajolet-Sedgwewick-digraphs are just [[binary relations]], \emph{not} [[digraphs]]\\ \hyperlink{Schriver2003}{SchrijverComOpt1st}&[[quiver]]&unusually hybrid formalization via \emph{families of ordered pairs}; Bondy-Murty formalise Schrijver's \emph{family} using a function called $\psi_D$&\emph{digraph}; beware that Schrijver-digraphs are \emph{not} [[digraphs]]&no aversion to the void here; moreover, note that SchrijverDigraphs$\simeq$Bondy-Murty-digraphs\\ \hyperlink{West2002}{West2002}&[[quiver]]&unusually hybrid functional-relational formalization via \emph{families of ordered pairs}: cf. \hyperlink{West2002}{Definition 1.4.2}; West is very explicit about allowing both loops and multiple directed edges&\emph{digraph}&beware that, as usual in the combinatorial literature, a ``path'' in \hyperlink{West2002}{Definition 1.4.6} is \emph{itself} a quiver, i.e. does not carry any parametrization-information, i.e. is not a map like [[paths]] are\\ \end{tabular} Note that ``kind of directed graph'' is a used in a loose, undefined sense, sufficiently clear from the context. \hypertarget{bidirected_graphs}{}\subsection*{{Bidirected graphs}}\label{bidirected_graphs} Roughly speaking, bidirected graphs are quivers in which \emph{each non-loop arrow gets decorated with \emph{two} elements drawn from a two-element set fixed in advanced, one thought to be attached to the arrow's tail, the other to its head}. Like for signed graphs, the elements of this two-element set are \emph{sometimes} interpreted to be \emph{signs} and equipped with arithmetical structure (essentially, the two-element set is taken to be a two-element [[group]]). (The treatment of \emph{loops} is slightly controversial in the combinatorical literature, prompting some ad-hoc-ery, and this is explicitly commented on at least once in the literature.) The category-theoretic literature seems not to have picked up on this so far, and could clarify the issue. Bidirected graphs are important in the theory of [[flows]] on [[graphs]]. \hypertarget{connections_to_category_theory}{}\subsection*{{Connections to category theory}}\label{connections_to_category_theory} Herein some evident aspects are pointed out explicitly. \hypertarget{underlying_quivers}{}\subsubsection*{{Underlying quivers}}\label{underlying_quivers} A basic connection is that for any category, its [[forgetful functor|underlying]] [[quiver]] is a directed graph. Another aspect is that a \emph{nonempty} [[digraph]] never is isomorphic to the [[quiver]] [[forgetful functor|underlying]] any category: such a quiver \emph{always} has a loop at each vertex, which is already enough to rule out any isomorphism. \hypertarget{an_application_of_directed_graphs_to_category_theory}{}\subsubsection*{{An application of directed graphs to category theory}}\label{an_application_of_directed_graphs_to_category_theory} Briefly, and from a slightly [[model theory|model theoretical]] point of view, the charm of this application is that [[pasting scheme|A. J. Power's pasting theorem]] is an example of a \emph{transfer} of knowledge from a \emph{theory without [[signature (in logic)|function symbols]]} to a \emph{theory with [[signature (in logic)|function symbols]]}. (The theory of [[digraphs]], strictly construed, is \emph{purely relational}, while [[higher category theory]] makes essential use of several [[signature (in logic)|function symbols]]). An example of a use of digraph theory in category theory is giving a rigorous justification of the notational practice of [[pasting diagrams]]. This was achieved in the late 1980s (cf. e.g. \hyperlink{Johnson1987}{Johnson 1987}, \hyperlink{Johnson1989}{Johnson 1989}, \hyperlink{Power1990}{Power 1990}). In this approach, parallel arcs or loops are of secondary importance, and sometimes expressly forbidden, so the work of Johnson and Power can be seen as a genuine application of graph theory to category theory. \hypertarget{all_quivers_deemed_irreflexive_by_lawvere}{}\subsubsection*{{\emph{All} quivers deemed irreflexive by Lawvere}}\label{all_quivers_deemed_irreflexive_by_lawvere} There is an article of [[William Lawvere]] which is relevant in one precise respect to a disambiguation page such as the present one: \emph{an unusual use of the adjective ``irreflexive''}. Therein, one reads (cf. (\hyperlink{GeneralizedGraphs}{Lawvere 1989}, page 272)) \begin{quote}% .. the elementary ``parallel process'' $E= \bullet\overset{\rightarrow}{\rightarrow}\bullet$ is a reflexive graph which happens to admit only one definition of composition making it into a category $\mathbf{P}$. .. Its [[actions]] $S^{\mathbf{P}^{\mathrm{op}}}$ are the \textbf{irreflexive} graphs (the negative is in a way appropriate even for those objects which happen to have loops at some point $p$, for morphisms are allowed to interchange \emph{any} two such loops). \end{quote} With ``the negative is in a way appropriate'' Lawvere explains the use of the strong negation \emph{irr-}, despite such an ``irreflexive graph'' being permitted to contain loops at \emph{some} of its vertices, which is obviously different from what one would expect from the usual sense of [[irreflexive relation]]. This is a usage in need of explanation, all the more against the backdrop of contemporary teaching where the term ``simple undirected graph'' is often literally defined as symmetric irreflexive relation (on the vertex set). Some authors have adopted this interesting variant sense of ``irreflexive'', prompting an additional use of the a modifier ``strict'' to form a composite ``strict irreflexive graph''. (cf. (\hyperlink{GraphsOfMorphismsOfGraphs}{Brown et al 2008}), which uses ``digraph'' as a synonym for ``strict irreflexive graph'', and this sense of ``digraph'' is precisely the one in [[digraph]]). In a sense, a [[digraph]] is a ``strictly-Lawvere-irreflexive graph''. From a graph-theoretical point of view, every digraph is a quiver, but not every quiver is a digraph (again, in the sense of \hyperlink{DG2nd}{Gutin and Bang-Jensen 2009}). \hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts} \begin{itemize}% \item [[digraph]] \item [[graph]] \item [[quiver]] \item [[n-quiver]] \item [[ribbon graph]] \item [[oriented graph]] \item [[signed graph]] \end{itemize} \hypertarget{references}{}\subsection*{{References}}\label{references} \begin{itemize}% \item A. Bondy, U.S.R. Murty: Graph Theory with Applications. Fifth Printing. North Holland 1982. \end{itemize} \begin{itemize}% \item Andr\'e{} Bouchet: \emph{Nowhere-Zero Integral Flows on a Bidirected Graph}. Journal of Combinatorial Theory, Series B 34, 279--292(1983) \end{itemize} \begin{itemize}% \item Gary Chartrand, Linda Lesniak, Ping Zhang: \emph{Graphs \& Digraphs}. Sixth edition. CRC Press. 2016 \end{itemize} \begin{itemize}% \item B. Csaba, D. K\"u{}hn, A. Lo, D. Osthus, A. Treglown: Proof of the 1-factorization and Hamilton decomposition conjectures. Memoirs of the American Mathematical Society, 244 (2016), monograph 1154, 170 pages \end{itemize} \begin{itemize}% \item [[Ronald Brown]], I. Morris, J. Shrimpton, C.D. Wensley: \emph{Graphs of morphisms of graphs}, The Electronic Journal of Combinatorics 15 (2008), A1 \end{itemize} \begin{itemize}% \item Richard Bumby and Dana Latch, \emph{Categorical constructions in graph theory}, lnternat. J. Math. and Math. Sci., Vol. 9 No. l (1986), 1-16. (\href{http://www.emis.de/journals/HOA/IJMMS/Volume9_1/791947.pdf}{pdf}) \item R. Diestel: \emph{Graph Theory}. Fourth Edition. Springer (2010) \end{itemize} \begin{itemize}% \item [[Philippe Flajolet]], Robert Sedgewick, \emph{Analytic Combinatorics}, 2009 (\href{http://algo.inria.fr/flajolet/Publications/book.pdf}{pdf}) \end{itemize} \begin{itemize}% \item [[Gregory Gutin]], [[Jørgen Bang-Jensen]]: \emph{Digraphs: Theory, Algorithms and Applications}. Springer Monographs in Mathematics. Second Edition (2009) \end{itemize} \begin{itemize}% \item [[Frank Harary]]: \emph{Graph Theory}. Addison Wesley. First Edition. (1969) \end{itemize} \begin{itemize}% \item [[Frank Harary]]: \emph{The notion of balance of a signed graph}. \item [[Michael Johnson]]: \emph{Pasting Diagrams in $n$-Categories with Applications to Coherence Theorems and Categories of Paths}, Doctoral Thesis, University of Sydney, 1987 \end{itemize} \begin{itemize}% \item [[Michael Johnson]]: \emph{The Combinatorics of $n$-Categorical Pasting}, Journal of Pure and Applied Algebra 62 (1989) \end{itemize} \begin{itemize}% \item [[William Lawvere]]: \emph{Qualitative Distinctions Between Some Toposes of Generalized Graphs}, Contemporary Mathematics 92 (1989) \end{itemize} \begin{itemize}% \item [[Eugene L. Lawler]]: \emph{Combinatorial Optimization: Networks and Matroids}, Holt, Rinehart and Winston. (1976) \end{itemize} \begin{itemize}% \item [[John Power]]: \emph{A 2-Categorical Pasting Theorem}, Journal of Algebra 129 (1990) \end{itemize} \begin{itemize}% \item [[Alexander Schrijver]]: \emph{Combinatorial Optimization}. Volume A. Springer. First Edition (2003) \end{itemize} \begin{itemize}% \item Douglas B. West: \emph{Introduction to Graph Theory}. Second Edition. Pearson Education. (2002) \end{itemize} \begin{itemize}% \item Thomas Zaslavsky: \emph{A Mathematical Bibliography of Signed and Gain Graphs and Allied Areas}, Electronic Journal of Combinatorics, Dynamic Surveys in Combinatorics, \#DS8. \end{itemize} \begin{itemize}% \item Thomas Zaslavsky: \href{http://people.math.binghamton.edu/zaslav/Bsg/index.html}{The Home Page of Signed, Gain, and Biased Graphs} \end{itemize} [[!redirects bidirected graph]] [[!redirects directed graphs]] [[!redirects Directed graph]] [[!redirects Directed graphs]] \end{document}