induced subgraphs
Author
Jimmy Cao
Last Updated
6 years ago
License
Creative Commons CC BY 4.0
Abstract
induced subgraphs question
induced subgraphs question
\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}