Problema de empaquetamiento generalizado en grafos con pocos $P_4$'s

ERICA HINRICHSEN; TORRES, PABLO; NATALÍ VANSTEENKISTE

Mendoza

Congreso; LXVIII Reunión Anual de Comunicaciones Científicas de la Unión Matemática Argentina; 2019

Universidad Nacional de Cuyo

Dado un grafo $G=(V,E)$ y vectores $\textbf{k},\Bell,\textbf{u}\in \Z_+^V$ con $\Bell \leq \textbf{u}$, decimos que una asignación $f:V\rightarrow\Z_{+}$ es un $(\textbf{k},\Bell,\textbf{u})$-\emph{empaquetamiento de} $G$ si para todo $v\in V$, se verifica: %$$\ell(v)\leq f(v)\leq u(v) \;\;\; \text{ y } \;\;\; f(N[v])\leq k(v)$$donde $N[v]$ denota la vecindad cerrada de $v$.%El Problema de Empaquetamiento Generalizado (\textbf{PEG}) consiste en determinar el \emph{número de} $(\textbf{k},\Bell,\textbf{u})$-\emph{empaquetamiento de} $G$, definido como$$L_{\textbf{k},\Bell,\textbf{u}}(G)= \max \left\{\sum_{v\in V} f(v): f \text{ es un }  (\textbf{k},\Bell,\textbf{u})-\text{empaquetamiento}\right\}.$$Este problema tiene como instancias particulares a la mayor parte de las diferentes variaciones de problemas de empaquetamiento de grafos estudiados en la literatura. Por ejemplo, los $k$-\emph{limited packings} \cite{GGHR10}corresponden al caso $k(v)=k$, $\ell(v)=0$ y $u(v)=1$ para todo $v \in V$. Si $\ell(v)=0$ y $u(v)\in\{0,1\}$ para todo $v \in V$, la asignación $f$ se denomina $(\textbf{k}, \mathcal{A})$-\emph{limited packings} \cite{DHL15a}, donde $\mathcal{A}=\{v\in V: u(v)=1\}$; y si$k(v)=u(v)=k$, $\ell(v)=0$ para todo $v\in V$, tenemos las $\{k\}$-\emph{packing functions} \cite{HL}.En este trabajo obtenemos una fórmula que permite calcular el número de $(\textbf{k},\Bell,\textbf{u})$-empaquetamiento de la unión y el join de dos grafos, en función de los parámetros de los grafos involucrados. A partir de este resultado, el estudio del problema en grafos generales puede reducirse a grafos modulares (conexos con complementos conexos).Analizamos el comportamiento del parámetro en grafos arañas y quasi  arañas,  grafos modulares de varias  familias de grafos \emph{con pocos} $P_4$'s. A partir de los resultados obtenidos se deriva un algoritmo lineal para el \textbf{PEG} sobre las instacias particulares correspondientes a las $\{k\}$-packing function en grafos $P_4$-tidy.Para el caso $\textbf{k}$ general y $\textbf{u}\geq \textbf{k}$, obtuvimos fórmulas para el número de  $(\textbf{k},\Bell,\textbf{u})$-\emph{empaquetamiento de} grafos arañas flacas y resultados parciales para grafos arañas gordas.