Researcher profile

Liliana Alcón

Liliana Alcón contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
2topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

4 published item(s)

preprint2022arXiv

On dually-CPT and strong-CPT posets

A poset is a containment of paths in a tree (CPT) if it admits a representation by containment where each element of the poset is represented by a path in a tree and two elements are comparable in the poset if and only if the corresponding paths are related by the inclusion relation. Recently Alcón, Gudiño and Gutierrez introduced proper subclasses of CPT posets, namely dually-CPT, and strongly-CPT. A poset $\mathbf{P}$ is dually-CPT, if and only if $\mathbf{P}$ and its dual $\mathbf{P}^{d}$ both admit a CPT representation. A poset $\mathbf{P}$ is strongly-CPT, if and only if $\mathbf{P}$ and all the posets that share the same underlying comparability graph admit a CPT representation. Where as the inclusion between Dually-CPT and CPT was known to be strict. It was raised as an open question by Alcón, Gudiño and Gutierrez whether strongly-CPT was a strict subclass of dually-CPT. We provide a proof that both classes actually coincide.

preprint2020arXiv

On $B_1$-EPG and EPT graphs

This research contains as a main result the prove that every Chordal $B_1$-EPG graph is simultaneously in the graph classes VPT and EPT. In addition, we describe structures that must be present in any $B_1$-EPG graph which does not admit a Helly-$B_1$-EPG representation. In particular, this paper presents some features of non-trivial families of graphs properly contained in Helly-$B_1$ EPG, namely Bipartite, Block, Cactus and Line of Bipartite graphs.

preprint2012arXiv

Pebbling in Split Graphs

Graph pebbling is a network optimization model for transporting discrete resources that are consumed in transit: the movement of two pebbles across an edge consumes one of the pebbles. The pebbling number of a graph is the fewest number of pebbles t so that, from any initial configuration of t pebbles on its vertices, one can place a pebble on any given target vertex via such pebbling steps. It is known that deciding if a given configuration on a particular graph can reach a specified target is NP-complete, even for diameter two graphs, and that deciding if the pebbling number has a prescribed upper bound is Π_2^P-complete. On the other hand, for many families of graphs there are formulas or polynomial algorithms for computing pebbling numbers; for example, complete graphs, products of paths (including cubes), trees, cycles, diameter two graphs, and more. Moreover, graphs having minimum pebbling number are called Class 0, and many authors have studied which graphs are Class 0 and what graph properties guarantee it, with no characterization in sight. In this paper we investigate an important family of diameter three chordal graphs called split graphs; graphs whose vertex set can be partitioned into a clique and an independent set. We provide a formula for the pebbling number of a split graph, along with an algorithm for calculating it that runs in O(n^β) time, where β=2ω/(ω+1)\cong 1.41 and ω\cong 2.376 is the exponent of matrix multiplication. Furthermore we determine that all split graphs with minimum degree at least 3 are Class 0.

preprint2011arXiv

Recognizing [h,2,1] graphs

An (h,s,t)-representation of a graph G consists of a collection of subtrees of a tree T, where each subtree corresponds to a vertex of G such that (i) the maximum degree of T is at most h, (ii) every subtree has maximum degree at mots s, (iii) there is an edge between two vertices in the graph G if and only if the corresponding subtrees have at least t vertices in common in T. The class of graphs that have an (h,s,t)-representation is denoted [h,s,t]. An undirected graph G is called a VPT graph if it is the vertex intersection graph of a family of paths in a tree. In this paper we characterize [h,2,1] graphs using chromatic number. We show that the problem of deciding whether a given VPT graph belongs to [h,2,1] is NP-complete, while the problem of deciding whether the graph belongs to [h,2,1]-[h-1,2,1] is NP-hard. Both problems remain hard even when restricted to $Split \cap VPT$. Additionally, we present a non-trivial subclass of $Split \cap VPT$ in which these problems are polynomial time solvable.