induced subgraphs
Author:
Jimmy Cao
Last Updated:
8 years ago
License:
Creative Commons CC BY 4.0
Abstract:
induced subgraphs question
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
induced subgraphs question
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
\documentclass{article}
\usepackage{fancyhdr} % Required for custom headers
\usepackage{lastpage} % Required to determine the last page for the footer
\usepackage{extramarks} % Required for headers and footers
\usepackage{graphicx} % Required to insert images
\usepackage{xcolor,colortbl}
\usepackage{listings}
\usepackage{ amssymb }
\usepackage{soul}
\usepackage{ amsmath }
\usepackage{courier}
\usepackage{color}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{bm}
% Margins
\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}
\definecolor{mygrayl}{gray}{0.85}
\usepackage{geometry}
\geometry{verbose,
lmargin=1.5in,
rmargin=1.5in
}
\linespread{1.1} % Line spacing
% Set up the header and footer
\pagestyle{fancy}
\fancyhf{}
\lhead{\hmwkAuthorName} % Top left header
\chead{} % Top center header
\rhead{Subgraph Construction Problem} % Top right header
\lfoot{\hmwkDueDate} % Bottom left footer
\cfoot{} % Bottom center footer
\rfoot{Page\ \thepage\ of\ \pageref{LastPage}} % Bottom right footer
\renewcommand\headrulewidth{0.4pt} % Size of the header rule
\renewcommand\footrulewidth{0.4pt} % Size of the footer rule
\setlength\parindent{0pt} % Removes all indentation from paragraphs
%----------------------------------------------------------------------------------------
% DOCUMENT STRUCTURE COMMANDS
% Skip this unless you know what you're doing
%----------------------------------------------------------------------------------------
% Header and footer for when a page split occurs within a problem environment
\newcommand{\enterProblemHeader}[1]{
\nobreak\extramarks{#1}{#1 continued on next page\ldots}\nobreak
\nobreak\extramarks{#1 (continued)}{#1 continued on next page\ldots}\nobreak
}
% Header and footer for when a page split occurs between problem environments
\newcommand{\exitProblemHeader}[1]{
\nobreak\extramarks{#1 (continued)}{#1 continued on next page\ldots}\nobreak
\nobreak\extramarks{#1}{}\nobreak
}
\setcounter{secnumdepth}{0} % Removes default section numbers
\newcounter{homeworkProblemCounter} % Creates a counter to keep track of the number of problems
\newcommand{\homeworkProblemName}{}
\newenvironment{homeworkProblem}[1][Problem \arabic{homeworkProblemCounter}]{ % Makes a new environment called homeworkProblem which takes 1 argument (custom name) but the default is "Problem #"
\stepcounter{homeworkProblemCounter} % Increase counter for number of problems
\renewcommand{\homeworkProblemName}{#1} % Assign \homeworkProblemName the name of the problem
\section{\homeworkProblemName} % Make a section in the document with the custom problem count
\enterProblemHeader{\homeworkProblemName} % Header and footer within the environment
}{
\exitProblemHeader{\homeworkProblemName} % Header and footer after the environment
}
\newcommand{\problemAnswer}[1]{ % Defines the problem answer command with the content as the only argument
\noindent\framebox[\columnwidth][c]{\begin{minipage}{0.98\columnwidth}#1\end{minipage}} % Makes the box around the problem answer and puts the content inside
}
\newcommand{\homeworkSectionName}{}
\newenvironment{homeworkSection}[1]{ % New environment for sections within homework problems, takes 1 argument - the name of the section
\renewcommand{\homeworkSectionName}{#1} % Assign \homeworkSectionName to the name of the section from the environment argument
\subsection{\homeworkSectionName} % Make a subsection with the custom name of the subsection
\enterProblemHeader{\homeworkProblemName\ [\homeworkSectionName]} % Header and footer within the environment
}{
\enterProblemHeader{\homeworkProblemName} % Header and footer after the environment
}
%----------------------------------------------------------------------------------------
% NAME AND CLASS SECTION
%----------------------------------------------------------------------------------------
\newcommand{\hmwkTitle}{Problem\ Set\ 8} % Assignment title
\newcommand{\hmwkDueDate}{Friday,\ July\ 1,\ 2016} % Due date
\newcommand{\hmwkClass}{CS\ 4820} % Course/class
\newcommand{\hmwkClassTime}{8:30am} % Class/lecture time
\newcommand{\hmwkClassInstructor}{Erkan} % Teacher/lecturer
\newcommand{\hmwkAuthorName}{Jimmy\ Cao} % Your name
\lstdefinelanguage{jcpseudo}{
keywords={new, function, return, if, while, else, structure, int, array, N, for, defined, as, break, continue},
ndkeywords={new, arraylist, quicksort},
sensitive=false,
comment=[l]{\#}
}
\lstset{ %
backgroundcolor=\color{white}, % choose the background color; you must add \usepackage{color} or \usepackage{xcolor}
basicstyle=\footnotesize, % the size of the fonts that are used for the code
breakatwhitespace=false, % sets if automatic breaks should only happen at whitespace
breaklines=true, % sets automatic line breaking
captionpos=b, % sets the caption-position to bottom
commentstyle=\color{mygreen}, % comment style
deletekeywords={...}, % if you want to delete keywords from the given language
escapeinside={\%*}{*)}, % if you want to add LaTeX within your code
extendedchars=true, % lets you use non-ASCII characters; for 8-bits encodings only, does not work with UTF-8
frame=single, % adds a frame around the code
keepspaces=true, % keeps spaces in text, useful for keeping indentation of code (possibly needs columns=flexible)
keywordstyle=\color{blue}\bfseries, % keyword style
language=jcpseudo, % the language of the code
otherkeywords={*,...}, % if you want to add more keywords to the set
numbers=left, % where to put the line-numbers; possible values are (none, left, right)
numbersep=5pt, % how far the line-numbers are from the code
numberstyle=\tiny\color{mygray}, % the style that is used for the line-numbers
rulecolor=\color{black}, % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. comments (green here))
showspaces=false, % show spaces everywhere adding particular underscores; it overrides 'showstringspaces'
showstringspaces=false, % underline spaces within strings only
showtabs=false, % show tabs within strings adding particular underscores
stepnumber=1, % the step between two line-numbers. If it's 1, each line will be numbered
stringstyle=\color{mymauve}, % string literal style
tabsize=2, % sets default tabsize to 2 spaces
title=\lstname % show the filename of files included with \lstinputlisting; also try caption instead of title
}
%----------------------------------------------------------------------------------------
\begin{document}
For every connected undirected graph $G$, there exists a function $s_G$ with two parameters $n$ and $m$ defined like so:
\bigskip
$s_G(n, m)$ = Maximum number of distinct, connected subgraphs of $G$ of order $n$, in which each vertex of $G$ is used in at most $m$ of these subgraphs.
For example, in this graph:
\includegraphics[width=0.5\textwidth]{Download__2_.png}
$s(1, 1) = |V| = 5$
$s(2, \infty) = |E| = 4$
$s(2, 1) = 1$ (in fact for all diameter-2 graphs, $s(2, m) = m$ up to $|E|$)
Another useful property:
$s(|V| - 1, \infty) = $ number of non-articulation points in the graph.
\bigskip
My question is, does this $s_G$ function unique determine graph $G$?
In other words, are two graphs $G$ and $G'$ isomorphic if and only if they have the same function?
And if so, if you restrict the second parameter $m$ to the two values of $\{1, \infty\}$ does this new function also do the same?
\end{document}